离散化与扫描线算法：高效求解矩形面积并问题

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[i+1] - xs[i]) * (ys[j+1] - ys[j])。我们的问题就从“求连续区域的面积”转化为了“求哪些小网格被覆盖，并累加它们的面积”。

然而，如果对每个小网格，都去检查它是否被N个原始矩形中的任意一个覆盖，复杂度是O(网格数 * N)。网格数最多是(2N * 2N)级别，即O(N²)，对于N=1000，网格数可达400万，再乘以N就是40亿，仍然太高。这就需要引入扫描线算法。我们可以固定一个维度（比如Y方向），在X方向上进行扫描。想象一条平行于X轴的直线，从下往上（沿Y轴）慢慢移动。当这条线穿过某个矩形的下边界时，这个矩形开始对覆盖有贡献；当穿过上边界时，贡献结束。在任意时刻，这条扫描线上被覆盖的X轴区间总长度是容易维护的。我们将扫描线在相邻两个离散化Y坐标之间移动时，覆盖的X区间长度是不变的，因此这一“层”的面积就是覆盖长度 * (ys[j+1] - ys[j])。

所以，完整的高效算法是：离散化 + 扫描线。离散化降低空间维度，扫描线利用区间加法动态维护覆盖长度，将复杂度优化到O(N² log N)或O(N²)，对于N=1000完全可行。

3. 算法细节与数据结构设计

3.1 数据读取与存储

首先，我们需要定义矩形的数据结构。每个矩形由左下角(x1, y1)和右上角(x2, y2)定义。在USACO的输入中，通常给出的是左下角和右上角坐标。注意，题目中的坐标可能是整数，且矩形是“覆盖”问题，边界上的点也算被覆盖，这会影响我们后续对区间开闭的处理。一个常见的技巧是，将矩形表示的覆盖区域视为左闭右开，下闭上开的区间，即[x1, x2) × [y1, y2)。这样处理可以避免边界重复计算，在扫描线算法中尤为常见。

struct Rectangle { int x1, y1, x2, y2; // (x1,y1)左下角, (x2,y2)右上角 }; vector<Rectangle> rects;

3.2 关键步骤一：坐标离散化

我们需要分别对X坐标和Y坐标进行离散化。收集所有矩形的x1, x2和y1, y2。

vector<int> 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_map<int, 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[i+1])和[ys[j], ys[j+1])对应一个网格。

3.3 关键步骤二：扫描线算法实现

扫描线算法沿着Y轴（纵轴）扫描。我们需要处理一些“事件”：当扫描线遇到一个矩形的下边界时，这个矩形在X轴上的覆盖区间[x1, x2)应该被激活；遇到上边界时，应该被移除。

我们可以为每个矩形生成两个事件：

1. 入事件：在y1处，区间[x1, x2)的覆盖次数+1。
2. 出事件：在y2处，区间[x1, x2)的覆盖次数-1。

将所有事件按Y坐标排序。然后，按顺序处理每个事件。我们需要一个数据结构来维护当前扫描线上，每个X区间被覆盖的次数。由于X坐标已经离散化，我们可以用一个数组cover来表示每个离散化X区间[xs[i], xs[i+1])被覆盖的次数。

处理流程：

1. 初始化cover数组为0，总面积area = 0。
2. 按Y坐标升序处理所有事件。设当前事件发生在y = current_y。
3. 首先，计算从上一次事件last_y到current_y之间，扫描线扫过的面积。这段高度是current_y - last_y。在这段高度内，X轴上的覆盖情况没有变化（因为事件都在Y坐标处发生）。因此，这段面积 =当前被覆盖的X轴总长度 * (current_y - last_y)。
   • 如何计算“当前被覆盖的X轴总长度”？遍历cover数组，只要cover[i] > 0，说明第i个X区间被至少一个矩形覆盖，就将它的长度(xs[i+1] - xs[i])累加起来。
4. 然后，处理所有发生在current_y处的事件：根据事件是入还是出，更新对应X区间的cover值。这里的关键是：一个原始矩形覆盖的X区间[x1, x2)，对应到离散化区间上，可能是多个连续的[xs[i], xs[i+1])。我们需要找到x1和x2对应的离散化索引idx1和idx2，然后对cover[idx1]到cover[idx2-1]进行区间加减操作。
5. 更新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[i+1])。节点维护两个信息：

1. cnt: 该节点对应的区间被完整覆盖的次数。
2. len: 该节点对应的区间中，被覆盖的长度（当cnt > 0时，len等于区间长度；否则，等于左右子节点len之和）。

这样，根节点的len就是当前被覆盖的X轴总长度，查询时间是O(1)。更新操作（对某个X区间进行+1或-1）是O(log N)。使用线段树后，总复杂度可以优化到O(N log N)。

对于信奥竞赛，N=1000，使用朴素的遍历方法（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; vector<int> xs, ys; vector<Event> 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()); // 建立坐标到索引的映射 map<int, 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区间被覆盖的次数 vector<int> 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[j+1] - 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; }

代码解析与避坑点：

1. 事件处理循环：外层while循环遍历所有事件。内层while循环处理同一Y坐标的所有事件。这种写法清晰地将“计算面积”和“更新覆盖状态”分开。
2. 区间开闭：我们将矩形视为[x1, x2)。在更新cover数组时，idx2是x2对应的索引，但实际覆盖的离散化区间是[idx1, idx2-1]。所以循环是for (int k = idx1; k < idx2; ++k)。这是最容易出错的地方之一，画个图就能理解：假设离散化点xs = {0, 5, 10}，矩形x1=0, x2=10。它覆盖了区间[0,5)和[5,10)，对应索引0和1。x_to_idx[10]得到2，所以循环应从0到1（即k < 2）。
3. 面积计算时机：我们在处理新Y坐标的事件之前，计算last_y到cur_y之间的面积。这意味着cover数组存储的是区间[last_y, cur_y)内的覆盖状态。这是正确的。
4. 初始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: vector<SegNode> tree; vector<int> xs; // 离散化X坐标值，用于计算区间长度 int n; // 计算节点p对应区间的实际长度 inline ll intervalLen(int p, int l, int r) const { return (xs[r+1] - 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; // 叶子节点且cnt=0 } else { tree[p].len = tree[p*2].len + tree[p*2+1].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*2+1, mid+1, r, ql, qr, val); push_up(p, l, r); } public: SegTree(const vector<int>& xs_vec) : xs(xs_vec) { n = xs.size() - 1; // 有n个区间 [xs[i], xs[i+1]) 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; vector<int> xs; vector<Event> 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()); // 建立坐标到索引的映射 map<int, 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; }

线段树实现要点：

1. cnt与len的含义：cnt记录该节点对应区间被“完整覆盖”的次数，len记录该区间内被覆盖的实际长度。这是扫描线线段树的核心。
2. push_up函数：这是关键。如果cnt > 0，说明整个区间被至少一个矩形完整覆盖，那么len就等于区间实际长度。否则，len等于两个子区间len之和（如果区间不是叶子节点）。注意，即使cnt == 0，该区间也可能被部分覆盖（通过子节点的cnt体现），所以需要从子节点汇总。
3. 区间更新：当更新操作完全覆盖某个节点区间时，直接修改它的cnt，然后push_up。不需要push_down操作，因为查询只关心根节点的总长度，且cnt信息已经通过push_up传递到了len。
4. 索引转换：线段树的叶子节点对应离散化区间[xs[i], xs[i+1])，索引从0到n-1（n = xs.size()-1）。所以add函数参数ql和qr是离散化索引，且是左闭右开区间[ql, qr)，对应线段树的闭区间[ql, qr-1]。

5. 调试技巧与常见问题实录

在实际编码和调试中，以下几个坑点几乎每个初学者都会遇到：

问题1：答案比预期小，尤其是矩形边界紧挨着的时候。

• 原因：最可能的原因是区间开闭处理错误。在离散化扫描线中，必须统一将矩形视为左闭右开区间[x1, x2)和[y1, y2)。如果你错误地将其视为闭区间[x1, x2]，那么当两个矩形在x=x2处相邻时，这个边界点会被两个矩形都计算一次，但在离散化后，这个点可能只对应一个无穷小的区间，导致面积丢失。
• 检查：画两个紧挨着的矩形，比如(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*2+1].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是开区间

  这避免了显式构建映射表，代码更短。

调试建议：

1. 从小数据开始：先测试一个矩形，面积是否正确。
2. 测试两个不重叠矩形：面积应为两者之和。
3. 测试两个完全重叠矩形：面积应为较大者。
4. 测试边相邻矩形：如上文的(0,0)-(10,10)和(10,0)-(20,10)，检查边界是否被正确计算。
5. 输出中间变量：在数组法中，打印出xs数组、每个事件的y和更新的cover数组，以及每次计算出的covered_len和增加的面积。在线段树法中，可以打印每次更新后根节点的len。这能帮你快速定位是离散化出错、事件处理出错还是面积计算出错。

6. 算法扩展与性能分析

时间复杂度分析：

• 数组法：离散化排序O(N log N)。事件排序O(N log N)。处理每个事件时，需要更新cover数组，最坏情况下更新O(N)个区间（当矩形横跨整个X轴时）。共有2N个事件，所以总复杂度为O(N²)。对于N=1000，计算量在1e6级别，在竞赛时间限制内通常是安全的。
• 线段树法：离散化和事件排序同上。每个事件更新线段树O(log N)，查询O(1)。总复杂度O(N log N)，效率更高，可以处理N=1e5甚至更大的数据。

空间复杂度：主要存储离散化坐标O(N)、事件O(N)和cover数组或线段树O(N)，都是O(N)级别。

算法扩展：

1. 周长并：P1856 [USACO5.5] 矩形周长 Picture。这是矩形面积并的姊妹题，需要计算所有矩形并集的轮廓线长度。思路类似扫描线，但需要同时维护覆盖次数和覆盖的区间段数。在扫描线从last_y移动到cur_y时，贡献的竖向周长是2 * 段数 * (cur_y - last_y)。横向周长则在每次覆盖长度发生变化时累加变化量的绝对值。需要更细致地维护线段树节点信息。
2. 三维体积并：原理类似，离散化三个维度，在二维平面上做扫描线，同时维护一个二维的覆盖情况。复杂度会更高，但思想一脉相承。
3. 非轴对齐矩形/多边形：扫描线算法依然适用，但“事件”不再是简单的Y坐标，而是多边形的边与扫描线的交点，需要处理边的插入、删除和排序，算法会更复杂（如Bentley-Ottmann算法）。

解决P1884这道题，掌握离散化与扫描线的思想，其价值远超题目本身。它教会我们如何将连续空间问题转化为离散事件问题，如何通过排序和数据结构动态维护状态。这种“事件驱动”和“状态维护”的思想，在解决许多计算几何、区间调度、资源分配问题上都有广泛应用。在信奥学习的道路上，这类题目是锻炼抽象思维和编码能力的绝佳材料。我建议在理解代码后，关闭参考，自己从头实现一遍，并尝试用线段树优化。过程中遇到的每一个错误，都是对算法理解更深一层的契机。