1. 项目概述从“种地”到“矩形覆盖”最近在带学生刷信奥信息学奥林匹克的题目遇到了一道非常经典的几何问题——USACO 2012年2月银组的P1884 “Overplanting S”。这道题乍一看描述是农夫约翰在种地实际上是一个考察离散化和扫描线算法的绝佳例题。很多初学者一看到二维平面上的矩形第一反应可能是暴力枚举每个点但数据范围矩形数量N ≤ 1000坐标绝对值 ≤ 1e9直接宣告了这种想法的死刑。坐标值巨大但矩形数量相对较少这几乎是明示我们要用离散化来“压缩”空间。这道题的核心是计算N个轴对齐矩形在平面上的并集面积。所谓轴对齐就是矩形的边都平行于X轴和Y轴。在计算机图形学、游戏开发碰撞检测、地理信息系统GIS中计算不规则形状的面积是常见需求而矩形并集是其中基础且重要的一环。用C解决它不仅能巩固STL容器如map,set,vector的使用更能深入理解“化连续为离散”、“化二维为一维”的算法思想。接下来我将拆解整个解题思路从暴力法的局限到离散化的引入再到扫描线算法的具体实现并附上详细的、可运行的C代码和关键调试技巧。2. 核心思路拆解为什么暴力法行不通我们先来最直观地感受一下题目的规模。假设我们想用最朴素的“染色法”创建一个巨大的二维布尔数组grid[x][y]遍历每个矩形将其覆盖的区域标记为true最后统计true的个数。这需要多大的内存呢坐标范围是[-1e9, 1e9]这意味着我们需要一个边长约为2e9的二维数组。即使每个元素只占1个字节所需内存也远远超过任何竞赛环境乃至普通计算机的限制。这还没考虑时间复杂度遍历每个矩形的每个点复杂度是O(N * 面积)更是不可接受。因此我们必须转换思路。注意到矩形只有1000个但坐标范围很大这启发我们使用离散化。离散化的本质是只关注那些“有意义”的坐标值。对于矩形面积并问题哪些坐标有意义显然是所有矩形的左、右边界X坐标和上、下边界Y坐标。因为面积的变化只发生在这些边界线上。我们可以把这些坐标排序、去重得到两个数组xs和ys。这样原本连续的、巨大的坐标平面就被这些关键坐标线划分成了一个个离散的、小的网格。每个网格是一个更小的矩形它的面积是(xs[i1] - xs[i]) * (ys[j1] - ys[j])。我们的问题就从“求连续区域的面积”转化为了“求哪些小网格被覆盖并累加它们的面积”。然而如果对每个小网格都去检查它是否被N个原始矩形中的任意一个覆盖复杂度是O(网格数 * N)。网格数最多是(2N * 2N)级别即O(N²)对于N1000网格数可达400万再乘以N就是40亿仍然太高。这就需要引入扫描线算法。我们可以固定一个维度比如Y方向在X方向上进行扫描。想象一条平行于X轴的直线从下往上沿Y轴慢慢移动。当这条线穿过某个矩形的下边界时这个矩形开始对覆盖有贡献当穿过上边界时贡献结束。在任意时刻这条扫描线上被覆盖的X轴区间总长度是容易维护的。我们将扫描线在相邻两个离散化Y坐标之间移动时覆盖的X区间长度是不变的因此这一“层”的面积就是覆盖长度 * (ys[j1] - ys[j])。所以完整的高效算法是离散化 扫描线。离散化降低空间维度扫描线利用区间加法动态维护覆盖长度将复杂度优化到O(N² log N)或O(N²)对于N1000完全可行。3. 算法细节与数据结构设计3.1 数据读取与存储首先我们需要定义矩形的数据结构。每个矩形由左下角(x1, y1)和右上角(x2, y2)定义。在USACO的输入中通常给出的是左下角和右上角坐标。注意题目中的坐标可能是整数且矩形是“覆盖”问题边界上的点也算被覆盖这会影响我们后续对区间开闭的处理。一个常见的技巧是将矩形表示的覆盖区域视为左闭右开下闭上开的区间即[x1, x2) × [y1, y2)。这样处理可以避免边界重复计算在扫描线算法中尤为常见。struct Rectangle { int x1, y1, x2, y2; // (x1,y1)左下角, (x2,y2)右上角 }; vectorRectangle rects;3.2 关键步骤一坐标离散化我们需要分别对X坐标和Y坐标进行离散化。收集所有矩形的x1, x2和y1, y2。vectorint xs, ys; for (auto rect : rects) { xs.push_back(rect.x1); xs.push_back(rect.x2); ys.push_back(rect.y1); ys.push_back(rect.y2); } // 排序并去重 sort(xs.begin(), xs.end()); xs.erase(unique(xs.begin(), xs.end()), xs.end()); sort(ys.begin(), ys.end()); ys.erase(unique(ys.begin(), ys.end()), ys.end());现在xs[i]和ys[i]就是离散化后的坐标值。我们可以建立从原始坐标到离散化索引的映射方便后续查找unordered_mapint, int x_id, y_id; for (int i 0; i xs.size(); i) x_id[xs[i]] i; for (int i 0; i ys.size(); i) y_id[ys[i]] i;离散化后我们得到(xs.size() - 1)个X方向区间和(ys.size() - 1)个Y方向区间。每个小区间[xs[i], xs[i1])和[ys[j], ys[j1])对应一个网格。3.3 关键步骤二扫描线算法实现扫描线算法沿着Y轴纵轴扫描。我们需要处理一些“事件”当扫描线遇到一个矩形的下边界时这个矩形在X轴上的覆盖区间[x1, x2)应该被激活遇到上边界时应该被移除。我们可以为每个矩形生成两个事件入事件在y1处区间[x1, x2)的覆盖次数1。出事件在y2处区间[x1, x2)的覆盖次数-1。将所有事件按Y坐标排序。然后按顺序处理每个事件。我们需要一个数据结构来维护当前扫描线上每个X区间被覆盖的次数。由于X坐标已经离散化我们可以用一个数组cover来表示每个离散化X区间[xs[i], xs[i1])被覆盖的次数。处理流程初始化cover数组为0总面积area 0。按Y坐标升序处理所有事件。设当前事件发生在y current_y。首先计算从上一次事件last_y到current_y之间扫描线扫过的面积。这段高度是current_y - last_y。在这段高度内X轴上的覆盖情况没有变化因为事件都在Y坐标处发生。因此这段面积 当前被覆盖的X轴总长度 * (current_y - last_y)。如何计算“当前被覆盖的X轴总长度”遍历cover数组只要cover[i] 0说明第i个X区间被至少一个矩形覆盖就将它的长度(xs[i1] - xs[i])累加起来。然后处理所有发生在current_y处的事件根据事件是入还是出更新对应X区间的cover值。这里的关键是一个原始矩形覆盖的X区间[x1, x2)对应到离散化区间上可能是多个连续的[xs[i], xs[i1])。我们需要找到x1和x2对应的离散化索引idx1和idx2然后对cover[idx1]到cover[idx2-1]进行区间加减操作。更新last_y current_y继续处理下一个事件。注意事项事件排序时如果多个事件Y坐标相同必须先处理入事件再处理出事件吗其实对于面积计算只要保证在计算current_y - last_y这段面积时cover数组反映的是[last_y, current_y)区间内的覆盖状态即可。通常我们将事件点视为“瞬间发生”计算面积时使用左闭右开区间[last_y, current_y)。因此当处理到current_y时应先计算面积此时cover是[last_y, current_y)区间的状态再处理current_y处的事件这些事件影响的是从current_y往后的状态。所以事件处理顺序是计算面积 - 处理本Y坐标的所有事件 - 更新last_y。3.4 数据结构优化避免O(N)遍历求覆盖长度在上述流程第3步每次计算覆盖长度都需要遍历整个cover数组长度最多2000在事件数最多2000个的情况下总复杂度是O(N³)可能有点慢。我们可以用线段树来优化。线段树的每个叶子节点对应一个离散化X区间[xs[i], xs[i1])。节点维护两个信息cnt: 该节点对应的区间被完整覆盖的次数。len: 该节点对应的区间中被覆盖的长度当cnt 0时len等于区间长度否则等于左右子节点len之和。这样根节点的len就是当前被覆盖的X轴总长度查询时间是O(1)。更新操作对某个X区间进行1或-1是O(log N)。使用线段树后总复杂度可以优化到O(N log N)。对于信奥竞赛N1000使用朴素的遍历方法O(N³)可能勉强能过取决于常数但为了掌握更普适的算法理解线段树优化是很有价值的。下面我将给出两种实现一种是易于理解的朴素数组法另一种是效率更高的线段树法。4. 代码实现与分步解析4.1 实现版本一离散化事件扫描数组维护这个版本逻辑清晰适合理解算法本质。#include iostream #include vector #include algorithm #include map using namespace std; typedef long long ll; // 面积可能很大用long long struct Event { int y, x1, x2; // 事件发生的y坐标影响的x区间[x1, x2) int type; // 1: 入事件矩形下边 -1: 出事件矩形上边 Event(int y, int x1, int x2, int type) : y(y), x1(x1), x2(x2), type(type) {} // 按y坐标排序 bool operator(const Event other) const { return y other.y; } }; int main() { int n; cin n; vectorint xs, ys; vectorEvent events; for (int i 0; i n; i) { int x1, y1, x2, y2; cin x1 y1 x2 y2; // 假设输入是左下角和右上角 // 转换为左闭右开区间 events.emplace_back(y1, x1, x2, 1); // 下边界入 events.emplace_back(y2, x1, x2, -1); // 上边界出 xs.push_back(x1); xs.push_back(x2); } // 1. 离散化X坐标 sort(xs.begin(), xs.end()); xs.erase(unique(xs.begin(), xs.end()), xs.end()); // 建立坐标到索引的映射 mapint, int x_to_idx; for (int i 0; i xs.size(); i) { x_to_idx[xs[i]] i; } // 2. 按Y坐标排序事件 sort(events.begin(), events.end()); // 3. cover数组记录每个离散化X区间被覆盖的次数 vectorint cover(xs.size() - 1, 0); ll total_area 0; int last_y events[0].y; // 第一个事件的y坐标 // 4. 处理事件 size_t i 0; while (i events.size()) { int cur_y events[i].y; // 计算从上个y到当前y之间的面积 if (cur_y last_y) { ll covered_len 0; for (int j 0; j cover.size(); j) { if (cover[j] 0) { covered_len (xs[j1] - xs[j]); } } total_area covered_len * (cur_y - last_y); } // 处理所有y坐标为cur_y的事件 while (i events.size() events[i].y cur_y) { Event e events[i]; // 找到x1和x2对应的离散化区间索引 int idx1 x_to_idx[e.x1]; int idx2 x_to_idx[e.x2]; // 注意x2对应的是开区间所以覆盖到idx2-1 for (int k idx1; k idx2; k) { cover[k] e.type; } i; } last_y cur_y; } cout total_area endl; return 0; }代码解析与避坑点事件处理循环外层while循环遍历所有事件。内层while循环处理同一Y坐标的所有事件。这种写法清晰地将“计算面积”和“更新覆盖状态”分开。区间开闭我们将矩形视为[x1, x2)。在更新cover数组时idx2是x2对应的索引但实际覆盖的离散化区间是[idx1, idx2-1]。所以循环是for (int k idx1; k idx2; k)。这是最容易出错的地方之一画个图就能理解假设离散化点xs {0, 5, 10}矩形x10, x210。它覆盖了区间[0,5)和[5,10)对应索引0和1。x_to_idx[10]得到2所以循环应从0到1即k 2。面积计算时机我们在处理新Y坐标的事件之前计算last_y到cur_y之间的面积。这意味着cover数组存储的是区间[last_y, cur_y)内的覆盖状态。这是正确的。初始last_y设置为第一个事件的Y坐标。在第一次循环时cur_y last_y所以不会计算面积高度差为0直接进入状态更新逻辑是自洽的。4.2 实现版本二离散化扫描线线段树优化当N更大时数组遍历求covered_len会成为瓶颈。下面给出线段树优化版本。这里实现一个简单的、适用于区间加法的线段树节点存储cnt覆盖次数和len覆盖长度。#include iostream #include vector #include algorithm #include map using namespace std; typedef long long ll; struct Event { int y, x1, x2, type; bool operator(const Event other) const { return y other.y; } }; // 线段树节点 struct SegNode { int cnt; // 区间被完整覆盖的次数 ll len; // 区间内被覆盖的长度 }; class SegTree { private: vectorSegNode tree; vectorint xs; // 离散化X坐标值用于计算区间长度 int n; // 计算节点p对应区间的实际长度 inline ll intervalLen(int p, int l, int r) const { return (xs[r1] - xs[l]); } void push_up(int p, int l, int r) { if (tree[p].cnt 0) { // 整个区间被完整覆盖 tree[p].len intervalLen(p, l, r); } else { // 未被完整覆盖长度等于左右儿子之和 if (l r) { tree[p].len 0; // 叶子节点且cnt0 } else { tree[p].len tree[p*2].len tree[p*21].len; } } } void update(int p, int l, int r, int ql, int qr, int val) { if (ql l r qr) { tree[p].cnt val; push_up(p, l, r); return; } int mid (l r) / 2; if (ql mid) update(p*2, l, mid, ql, qr, val); if (qr mid) update(p*21, mid1, r, ql, qr, val); push_up(p, l, r); } public: SegTree(const vectorint xs_vec) : xs(xs_vec) { n xs.size() - 1; // 有n个区间 [xs[i], xs[i1]) tree.resize(4 * n); } // 对外接口更新区间[ql, qr)注意是左闭右开 // ql, qr 是离散化区间的索引0-based void add(int ql, int qr, int val) { if (ql qr) return; // 空区间 // 线段树操作的是闭区间所以qr-1 update(1, 0, n-1, ql, qr-1, val); } ll query() const { return tree[1].len; // 根节点的len就是总覆盖长度 } }; int main() { int n; cin n; vectorint xs; vectorEvent events; for (int i 0; i n; i) { int x1, y1, x2, y2; cin x1 y1 x2 y2; events.push_back({y1, x1, x2, 1}); events.push_back({y2, x1, x2, -1}); xs.push_back(x1); xs.push_back(x2); } // 离散化X坐标 sort(xs.begin(), xs.end()); xs.erase(unique(xs.begin(), xs.end()), xs.end()); // 建立坐标到索引的映射 mapint, int x_to_idx; for (int i 0; i xs.size(); i) { x_to_idx[xs[i]] i; } // 事件排序 sort(events.begin(), events.end()); // 初始化线段树 SegTree seg_tree(xs); ll total_area 0; int last_y events[0].y; size_t i 0; while (i events.size()) { int cur_y events[i].y; // 计算面积 if (cur_y last_y) { ll covered_len seg_tree.query(); total_area covered_len * (cur_y - last_y); } // 处理同一y的所有事件 while (i events.size() events[i].y cur_y) { Event e events[i]; int idx1 x_to_idx[e.x1]; int idx2 x_to_idx[e.x2]; seg_tree.add(idx1, idx2, e.type); i; } last_y cur_y; } cout total_area endl; return 0; }线段树实现要点cnt与len的含义cnt记录该节点对应区间被“完整覆盖”的次数len记录该区间内被覆盖的实际长度。这是扫描线线段树的核心。push_up函数这是关键。如果cnt 0说明整个区间被至少一个矩形完整覆盖那么len就等于区间实际长度。否则len等于两个子区间len之和如果区间不是叶子节点。注意即使cnt 0该区间也可能被部分覆盖通过子节点的cnt体现所以需要从子节点汇总。区间更新当更新操作完全覆盖某个节点区间时直接修改它的cnt然后push_up。不需要push_down操作因为查询只关心根节点的总长度且cnt信息已经通过push_up传递到了len。索引转换线段树的叶子节点对应离散化区间[xs[i], xs[i1])索引从0到n-1n xs.size()-1。所以add函数参数ql和qr是离散化索引且是左闭右开区间[ql, qr)对应线段树的闭区间[ql, qr-1]。5. 调试技巧与常见问题实录在实际编码和调试中以下几个坑点几乎每个初学者都会遇到问题1答案比预期小尤其是矩形边界紧挨着的时候。原因最可能的原因是区间开闭处理错误。在离散化扫描线中必须统一将矩形视为左闭右开区间[x1, x2)和[y1, y2)。如果你错误地将其视为闭区间[x1, x2]那么当两个矩形在xx2处相邻时这个边界点会被两个矩形都计算一次但在离散化后这个点可能只对应一个无穷小的区间导致面积丢失。检查画两个紧挨着的矩形比如(0,0)-(10,10)和(10,0)-(20,10)。正确并集面积应为200。如果你的程序输出190就是开闭问题。解决确保事件处理逻辑和区间更新逻辑匹配。在数组法中更新循环是for (k idx1; k idx2; k)。在线段树法中add(idx1, idx2, val)中的idx2是开区间。问题2使用线段树时push_up函数中l r的情况处理不当导致错误。现象程序运行异常结果不对。原因在push_up中当cnt 0时如果当前节点是叶子节点(l r)那么它的len应该为0因为它代表一个最小的离散化区间没有被覆盖。如果没有这个判断叶子节点会尝试访问不存在的子节点。解决在push_up中加上叶子节点的判断if (tree[p].cnt 0) { tree[p].len intervalLen(p, l, r); } else { if (l r) { tree[p].len 0; } else { tree[p].len tree[p*2].len tree[p*21].len; } }问题3坐标值很大面积需要用long long。原因坐标范围±1e9离散化后区间长度最大可达2e9高度差也是这个量级相乘可能达到4e18远超int范围约2e9。解决所有与面积、长度相关的变量如total_area,covered_len, 线段树的len都使用long long。在C中1e9是double类型与int运算可能会出问题建议直接使用long long存储坐标或进行强制转换。问题4事件排序时同一Y坐标的事件处理顺序有影响吗分析在我们的逻辑中处理到cur_y时先计算last_y到cur_y的面积用的是之前的覆盖状态再处理cur_y处的事件。因此cur_y处所有事件无论是入还是出都是同时生效的它们影响的是cur_y之后的高度区间。所以同一Y坐标的事件任意顺序更新cover数组或线段树对最终结果都没有影响。因为计算面积时它们都还未生效。这使得代码更简单。问题5离散化映射用map还是unordered_map建议使用map或对离散化数组进行二分查找。unordered_map在数据量小时也可以但需要处理哈希。一个更简洁的方法是在排序去重后使用lower_bound进行二分查找int idx1 lower_bound(xs.begin(), xs.end(), x1) - xs.begin(); int idx2 lower_bound(xs.begin(), xs.end(), x2) - xs.begin(); // 注意x2是开区间这避免了显式构建映射表代码更短。调试建议从小数据开始先测试一个矩形面积是否正确。测试两个不重叠矩形面积应为两者之和。测试两个完全重叠矩形面积应为较大者。测试边相邻矩形如上文的(0,0)-(10,10)和(10,0)-(20,10)检查边界是否被正确计算。输出中间变量在数组法中打印出xs数组、每个事件的y和更新的cover数组以及每次计算出的covered_len和增加的面积。在线段树法中可以打印每次更新后根节点的len。这能帮你快速定位是离散化出错、事件处理出错还是面积计算出错。6. 算法扩展与性能分析时间复杂度分析数组法离散化排序O(N log N)。事件排序O(N log N)。处理每个事件时需要更新cover数组最坏情况下更新O(N)个区间当矩形横跨整个X轴时。共有2N个事件所以总复杂度为O(N²)。对于N1000计算量在1e6级别在竞赛时间限制内通常是安全的。线段树法离散化和事件排序同上。每个事件更新线段树O(log N)查询O(1)。总复杂度O(N log N)效率更高可以处理N1e5甚至更大的数据。空间复杂度主要存储离散化坐标O(N)、事件O(N)和cover数组或线段树O(N)都是O(N)级别。算法扩展周长并P1856 [USACO5.5] 矩形周长 Picture。这是矩形面积并的姊妹题需要计算所有矩形并集的轮廓线长度。思路类似扫描线但需要同时维护覆盖次数和覆盖的区间段数。在扫描线从last_y移动到cur_y时贡献的竖向周长是2 * 段数 * (cur_y - last_y)。横向周长则在每次覆盖长度发生变化时累加变化量的绝对值。需要更细致地维护线段树节点信息。三维体积并原理类似离散化三个维度在二维平面上做扫描线同时维护一个二维的覆盖情况。复杂度会更高但思想一脉相承。非轴对齐矩形/多边形扫描线算法依然适用但“事件”不再是简单的Y坐标而是多边形的边与扫描线的交点需要处理边的插入、删除和排序算法会更复杂如Bentley-Ottmann算法。解决P1884这道题掌握离散化与扫描线的思想其价值远超题目本身。它教会我们如何将连续空间问题转化为离散事件问题如何通过排序和数据结构动态维护状态。这种“事件驱动”和“状态维护”的思想在解决许多计算几何、区间调度、资源分配问题上都有广泛应用。在信奥学习的道路上这类题目是锻炼抽象思维和编码能力的绝佳材料。我建议在理解代码后关闭参考自己从头实现一遍并尝试用线段树优化。过程中遇到的每一个错误都是对算法理解更深一层的契机。