扫描线+离散化+线段树：矩形面积并算法详解与卡常技巧

"扫描线 + 离散化 + 线段树 + 二分 + 卡常"，这几个词垒在一起，懂行的老哥嘴角已经开始上扬了：今天又要被几何题折磨。我刷了这么多年 OJ，凡是题目标签长成这样的，基本就是那种"单看每个知识点都会，一合并就崩"的缝合怪。这类题通常不会给你一个用单一板子秒过的模型，它要求你对扫描线的理解足够深，对线段树的记号足够熟，对离散化的边界足够敏感，最后还得有点卡常的功底，否则同样的复杂度，别人 AC，你 TLE。

这篇文章我打算直接用一套完整的"矩形面积并"为骨架，把这个组合模型从头到尾按实际写题的过程拆一遍。无论你是在准备竞赛、刷考研复试机试，还是单纯想搞懂这几个算法为什么总爱一起出现，都应该能在这篇里找到可以直接抄作业的代码和踩坑记录。

1. 扫描线算法为什么必配离散化和线段树：一个把二维变一维的经典套路

1.1 扫描线在"扫"什么：从暴力到事件流

先说你最关心的问题：扫描线为什么能算矩形面积并？

最暴力的思路是开二维差分数组，枚举每个整数点打标记，最后统计被覆盖的格子数。坐标范围小的时候没问题，一旦坐标到 1e9，二维数组直接把你内存条干废。就算用离散化，把坐标压缩到 2n 个点，二维数组规模也是 O(n^2)，n 到 1e5 时依然完全不可行。

扫描线的核心观察是：把每个矩形拆成左右两条竖边，左边那条让它"进入"覆盖状态，右边那条让它"退出"覆盖状态。然后让一条竖直的线从 x 轴最左边往右推。x 在两个事件之间移动时，y 轴上被覆盖的区间集合是不变的，所以这一段区域的面积可以表达成"当前覆盖总长度 × x 方向上的位移"。你只需要维护好 y 轴上的覆盖状态，随着 x 推进到不同事件时更新它，并把每一小段的面积累加进答案。

这就是典型的"把二维问题降成一维问题"：二维上的"扫"，变成了一维上的"动态区间状态维护"。而这个一维覆盖状态，需要支持的操作是"区间整体加 1 或减 1"和"查询整个区间被覆盖的总长度"，这两件事恰好都是线段树的舒适区。

1.2 离散化的本质：把连续坐标压缩成下标

但是 y 坐标是 1e9 范围的实数或整数，没法直接开数组。解决方案就是把所有矩形的 y1 和 y2 全部收集起来，排序去重，得到一个长度最多 2n 的坐标序列 xs[1..m]。之后所有跟 y 有关的操作都只围绕这些边界值展开。

这里要特别强调一个最容易绕晕的点：离散化之后，线段树的节点维护的不是"点"，而是"区间"。我习惯把 xs[i] 到 xs[i+1] 这一段称为"区间编号 i"。坐标集合有 m 个数，那么线段树管辖的区间编号就是 1 到 m-1。以后看到 update(l, r)，心里要默认这里的 l 和 r 是区间编号，不是坐标点。这个思维切换不过去，后面写代码十有八九要在边界上翻车。

做个生活化类比：你不会关心高速公路上每一米的收费情况，只需要在被收费站分隔开的若干路段上记录状态。收费站就是离散化点，路段就是区间编号。

1.3 线段树到底在维护什么：覆盖次数与长度的关系

线段树节点需要存两个关键值。一个是 cnt，表示这个区间被多少个矩形"完整覆盖"；另一个是 len，表示这个区间被覆盖的总长度。注意"完整覆盖"这四个字，它是整个 pushup 逻辑的灵魂。

cnt 只在 update 时对完全命中的节点做整体加减，它不需要下传给子节点，因为矩形覆盖的特点决定了：一个父区间要么被完整标记，要么靠子区间拼接出具体覆盖情况。而 len 才是真正对外输出的数据，它决定了面积累加时的"宽度"。

这两者的关系在 pushup 里体现得淋漓尽致，也是很多人背了代码却一直想不明白的地方。下一节我直接把完整代码甩出来，逐行拆给你看。

2. 手写一遍矩形面积并：从事件生成到线段树更新的完整核心代码

先上全代码，这段是后面所有讨论的载体。顺手把注释写得详细一点，方便你对号入座。

#include <bits/stdc++.h> using namespace std; const int MAXN = 200010; // 假设 n <= 100000，事件数 2n struct Event { int x, y1, y2, op; // op=1 进入, op=-1 退出 } e[MAXN << 1]; int xs[MAXN << 1]; // 所有 y 坐标，用于离散化 int cnt[MAXN * 4 + 10]; // 完整覆盖次数 int segLen[MAXN * 4 + 10]; // 被覆盖总长度 inline bool cmpEvent(const Event& a, const Event& b) { if (a.x != b.x) return a.x < b.x; return a.op > b.op; // 同一 x：先进入，后退出 } inline void pushup(int p, int l, int r) { if (cnt[p]) { segLen[p] = xs[r + 1] - xs[l]; } else if (l == r) { segLen[p] = 0; } else { segLen[p] = segLen[p << 1] + segLen[p << 1 | 1]; } } void update(int p, int l, int r, int ql, int qr, int val) { if (ql <= l && r <= qr) { cnt[p] += val; pushup(p, l, r); return; } int mid = (l + r) >> 1; if (ql <= mid) update(p << 1, l, mid, ql, qr, val); if (qr > mid) update(p << 1 | 1, mid + 1, r, ql, qr, val); pushup(p, l, r); } int main() { int n; while (scanf("%d", &n) != EOF) { int totX = 0, totE = 0; for (int i = 0; i < n; ++i) { int x1, y1, x2, y2; scanf("%d%d%d%d", &x1, &y1, &x2, &y2); e[++totE] = {x1, y1, y2, 1}; e[++totE] = {x2, y1, y2, -1}; xs[++totX] = y1; xs[++totX] = y2; } sort(e + 1, e + 1 + totE, cmpEvent); sort(xs + 1, xs + 1 + totX); int m = unique(xs + 1, xs + 1 + totX) - (xs + 1); // 线段树维护的是区间编号 1..m-1 long long ans = 0; for (int i = 1; i <= totE; ++i) { if (i > 1) { ans += 1LL * segLen[1] * (e[i].x - e[i - 1].x); } int L = lower_bound(xs + 1, xs + 1 + m, e[i].y1) - xs; int R = lower_bound(xs + 1, xs + 1 + m, e[i].y2) - xs - 1; if (L <= R) update(1, 1, m - 1, L, R, e[i].op); } printf("%lld\n", ans); } return 0; }

这段代码我实测在很多 OJ 上都是可行的。下面把几个关键决策讲透。

2.1 矩形的四条边如何变成有序事件

读入矩形时，我生成两条事件：左边界 (x1, y1, y2, +1) 和右边界 (x2, y1, y2, -1)。事件结构体里的 y1、y2 在排序时根本用不上，它们的作用是等离散化完成后，把 y 坐标转换成区间编号再传到线段树里。很多模板会在事件里直接存离散化后的下标，那样更快，我后面讲卡常时会说，但你第一次写的时候，直接拿原始坐标做 lower_bound 反而更好懂，不容易错。

排序规则第一关键字 x 升序是显然的，第二关键字 op 降序（先 +1 后 -1）是很多新手忽略的。同样一个 x 位置，假如同时有矩形退出和进入，你必须先处理进入事件，再处理退出事件。为什么？给你留个悬念，第 5 节我会专门复盘一个因为这里写反而在周长并题上卡到怀疑人生的真实案例。

2.2 线段树节点设计与 pushup 的精髓

看 pushup 那三行，看懂它们，扫描线线段树就通了一半。

如果 cnt[p] > 0，说明整个节点管辖的区间被至少一个矩形完整覆盖了，那么不管子节点什么状态，这个区间的覆盖长度就是物理长度 xs[r+1] - xs[l]。

如果 cnt[p] == 0，说明当前节点没有被完整覆盖，那真实覆盖情况只能由子节点的覆盖长度拼出来，所以取左右子树 segLen 之和。如果 l == r 这种叶子节点也出现 cnt == 0，那说明这个区间确实一根毛都没被盖住，长度就是 0。

重点来了：这段 pushup 完全没有 pushdown，也就是 child 的 cnt 在父节点 cnt 变化时不做任何同步。这在普通懒标记线段树里是大忌，但扫描线这里是对的。原因是矩形覆盖只会"完整覆盖"一个节点管辖的整个区间，不可能出现"父节点被覆盖了一半，需要把半个区间标记传给子节点"的情况。父节点如果没被完整覆盖，那就不管，让子节点各算各的。一旦父节点被完整覆盖，它的 len 直接取物理长度，也不再依赖子节点数据。这就是为什么 cnt 可以"不往上传也不往下传"，还不会算错。

2.3 update 区间为什么右边界要减一：离散化映射的细节

这是新手最容易卡住的地方。坐标去重后，xs 里有 m 个不同的 y 值，它们构成了 m-1 个区间段：第 i 段是 [xs[i], xs[i+1]]。所以线段树的节点区间是 1..m-1。

当你要把一个矩形的 y1 到 y2 这段标记为覆盖时，左边界对应的区间编号是 lower_bound(xs, y1)，右边界对应的区间编号是 lower_bound(xs, y2) - 1。为什么右边要减一？因为 y2 作为右边界点，它在分段里出现的身份是"下一段的左端点"。假如 y2 在 xs 里的下标是 5，那它结束的区间段其实是编号 4，也就是 [xs[4], xs[5]]。不减一，你就把 [xs[5], xs[6]] 这一段也盖进去了，面积直接虚胖。

这个减一操作在扫描线代码里非常经典，几乎每个题解都会提，但真正到赛场上自己写时，一紧张还是会忘了减。我给自己的口诀是：左闭右开，区间编号等于"左端点下标"到"右端点下标减一"。

另外，如果矩形退化成一条线，即 y1 == y2，那么 L 会大于 R，update 直接跳过，物理面积是零，安全起见也不会崩。这种退化 case 平时没人提，但数据刁钻的时候能救你一命。

3. 线段树上二分：两个高频场景与实现细节

很多人看到"seg+二分"会以为是外层套二分的常规思路，但扫描线题里真正高频的是"线段树上二分"，也就是利用线段树天然的二分结构，在一次 O(log n) 的递归里完成某种"第 k 个"查询。下面两个场景我实际刷题中遇到很多次。

3.1 场景一：查询第 k 个被覆盖点的位置（树上二分）

假设我在扫描线推进过程中，想知道"当前 x 位置，y 轴上从左往右数第 k 个单位长度的覆盖点，到底落在哪个坐标区间"。这个需求在统计交叠区间、分布分位数之类的变体题里很常见。

数据库结构完全不需要改动，就用上面的 segLen。递归查找的思路和权值线段树找第 k 大一模一样：

int findKth(int p, int l, int r, long long k) { if (l == r) return l; // 返回区间编号 int mid = (l + r) >> 1; if (segLen[p << 1] >= k) { return findKth(p << 1, l, mid, k); } else { return findKth(p << 1 | 1, mid + 1, r, k - segLen[p << 1]); } }

调用前保证 1 <= k <= segLen[1]。为什么左子树的 segLen 能直接当判断依据？因为 segLen 保存的是左半部分所有覆盖段的总长度，而"从左往右第 k 个被覆盖单位"，如果 k 落在左子树的覆盖总长度以内，那它必然在左半区；否则减去左半的覆盖长度，去右半区继续找。

这里的 k 一定要用 long long，因为坐标差本身可以到 1e9，而多个矩形叠加后覆盖长度可能膨胀到很大。很多选手在这个小地方用 int 吃 WA，十分可惜。

3.2 场景二：二分答案套扫描线验证的万能 check

另一种常见组合是"外层对答案二分，内层用扫描线做可行性检查"。这类题往往有一个单调的答案，比如最大空隙、最小覆盖窗口。你每二分到一个 mid，就把所有覆盖体转换成扫描线事件，跑一次覆盖状态的检查，看是否满足题目条件。整体复杂度是 O(log V * n log n)，V 是答案值域。

这种双层结构对常数极其敏感。我见过不少题复杂度看起来能过，但实际上内外两层乘起来，运行时间翻了三倍多，直接被时限按在地上摩擦。所以凡是看到"二分答案 + 扫描线"的题，还没开始写，就该想想怎么把 check 函数做薄，这也是我下一节为什么要专门聊卡常的根本原因。

4. 卡常实录：六个让我从 TLE 到 AC 的落地技巧

卡常是一个很现实的技术。先别急着学什么奇技淫巧，排序、离散化、线段树、读入四处的常规优化先做到位，大多数 TLE 就已经解决了。

4.1 读入优化：fread 快读模板

当 n 到 1e5 时，cin 即使开了 ios::sync_with_stdio(false) 也还能凑合；n 到 1e6 或者多 case 叠加，cin 会明显拖后腿。我常用的 fread 快读模板长这样：

const int BUF_SIZE = 1 << 20; char buf[BUF_SIZE]; int p1 = 0, p2 = 0; inline char nc() { if (p1 == p2) { p2 = (p1 = 0) + fread(buf, 1, BUF_SIZE, stdin); if (p1 == p2) return EOF; } return buf[p1++]; } inline int readInt() { int x = 0; char c = nc(); while (c < '0' || c > '9') c = nc(); while (c >= '0' && c <= '9') { x = x * 10 + (c - '0'); c = nc(); } return x; }

注意这段模板读的是整数，坐标如果是实数还要另外改。但我的忠告是：不是所有题都需要快读。数据量低于 5e5 个整数时，cin + 关闭同步足够；超过 1e6 再用 fread。为了卡常去写快读，结果快读本身写错或者凭空引入 bug，才是得不偿失。

4.2 离散化映射一次性预处理：别在 update 里反复 lower_bound

第 2 节的完整代码里，我在每个事件都现场做了两次 lower_bound。这是为了教学清晰，实际大数据的题里，这种做法是第一个该优化的点。

事件量是 2n，每次 lower_bound 是 O(log n)，n 到 1e6 时就是四百万次二分，时间浪费得很明显。正确做法是：完成离散化之后，把所有事件的 y1、y2 一次性转换成编号 L、R，存进事件结构体或者独立数组。后续 update 直接取整型下标，整个扫描过程不再碰 lower_bound。这一项的实际收益常常比读入优化更大，是扫描线卡常的首选目标。

4.3 线段树实现层面的减法：数组化、内联化、最小化 memset

写线段树时，用结构体对象数组本身没问题，但访问 tree[p].cnt 比直接访问全局数组 cnt[p] 多一层间接寻址，在千万级递归调用下差距不可忽视。我习惯把 cnt 和 segLen 拆成两个全局数组，pushup 和 update 都定义成 inline 函数，递归里尽量用 int 运算，只有需要返回长度结果时才用 long long。

多组数据时还有一个隐蔽的坑：对整棵 4 * MAXN 的数组做 memset。如果 MAXN 开得很大，而每次实际用到的 m 只有几百，那 memset 的浪费就非常可观。正确姿势是按实际用到的节点数 4 * m + 5 清零。这个细节我在一次 n=1e5 的多 case 题里实测过，能差出几倍的运行时间。

4.4 卡常的次序：先找算法瓶颈再动手

我见过有人把代码从 cin 改成 fread 后洋洋得意，结果 TLE 依旧。后来才发现瓶颈根本不在读入，而是事件排序的比较函数里不小心写了慢操作，或者 lower_bound 反复调用太多次。所以我给卡常定的第一原则：先判断这道题是 IO 密集还是计算密集，再决定先优化哪一块。n 只有 1e5 时，读入和排序都不是瓶颈，真正的大头是线段树递归深度；n 到 1e6 时，优先查离散化映射的重复计算和数组清空。顺序搞反，越卡越废。

5. 常见问题与排查技巧：这些坑我基本都踩过

5.1 高频 bug 速查表

下面这个表覆盖了我做扫描线题时遇到的大部分错误。写代码前扫一眼，排错时对号入座，能省很多时间。

5.2 手工对拍：如何快速定位扫描线的错

手头没有现成数据生成器的时候，我习惯用最原始的对拍方案：写一个暴力程序，用二维 bool 数组模拟，坐标范围限制在 0..30，暴力标记每个矩形盖住的格子；主程序输出面积并结果，随机造数据后两者对比。一旦不一致，固定这组数据，把暴力程序的覆盖矩阵打出来，再对照扫描线循环里每一步的 segLen 变化，基本一眼就能看出是哪条边对应的区间映射错了。

调试时我的原则是分模块验证。先单独验证离散化映射对不对，再验证事件排序规则，最后才怀疑线段树 update。很多选手一上来就盯着线段树 debug，实际上坐标映射出错的概率往往更高。把定位范围一步步缩小，比对着整个程序发呆效率高得多。

5.3 一次真实 debug 复盘：同一 x 坐标的事件顺序

最后聊一个我印象很深的坑。有一道求周长并的题，我一直 WA，随机对拍又拍不出差别，因为随机数据很少出现两条边 x 坐标完全相同的情况。后来我故意造了一组稠密数据，问题立刻暴露了：同一 x 坐标处，一个矩形的右边界和另一个矩形的左边界同时存在，我的排序把"退出"排在了"进入"前面。

对面积并来说，这个顺序碰巧不会错，因为面积只关心"每个 x 区间结束后的状态"。但周长并每次移动要统计水平方向的长度变化，事件顺序一旦反了，该算进去的横边就被吞掉。排查过程也很典型：先在每个事件处打印 update 后的 segLen[1]，用期望值对比，再用肉眼检查排序后的事件序列，最后把 cmp 改成 op 降序，AC。这件事再次印证：扫描线的正确性极度依赖事件排序的稳定性，很多题不会给你明显的 WA 特征，只有对拍加重现、构造极端数据，才能把这种隐藏 bug 揪出来。

写这种缝合题，我最深的体会是：不要觉得自己会了扫描线、会了离散化、会了线段树，就等于会做这个题。真正难的是把它们缝在一起时，你敢不敢在 update 的区间下标上打一个断点，敢不敢对着对拍结果承认"排序规则有问题"。这类题刷多了特别练内功，因为它逼着你把每个算法的适用边界都问一遍：离散化到区间编号的映射、cnt 的 pushup 语义、事件排序的稳定性、卡常的优先级，任何一个地方模糊，都会在数据最刁钻的时候打脸。先把这套标准模型吃透，再去看变种题，你会发现大部分题目无非是在这几件事上做一些加减法而已。