刷题刷到一定程度，几乎绕不开 P5490 这道扫描线模板题。题目内容总结起来就一句话：给你最多十万个矩形，坐标范围撑到 1e9，求它们覆盖的总面积，重叠部分只算一次。第一次做这类题的人，最直观的想法往往是二维数组标记或者暴力容斥，但看到这个数量级基本就断了念想。这道题的标准解法就是扫描线加线段树加离散化三件套，算得上计算几何和数据结构结合的经典样板。这篇文章就围绕这道模板题，把扫描线为什么能算面积、线段树到底在维护什么、离散化之后哪些边界必须小心，全部讲透。
这篇文章适合这几类人：刚学完基础线段树、想进阶区间维护模型的竞赛选手；对矩形面积并、周长并这类几何题只闻其名没见过代码的人；以及那些已经能 AC 但因为模板背得不理解原理、换个题就写不出来的朋友。我会从题目本身出发，先推算法思路，再逐段拆代码，最后把容易踩的坑整理成一份可以直接拿去用的排查清单。
1. 题目与问题定位
1.1 P5490 这道模板题到底在问什么
题目输入一个整数 n，接下来 n 行每行四个整数 x1, y1, x2, y2，表示一个矩形的左下角坐标和右上角坐标。要求输出所有矩形覆盖的总面积，多个矩形重叠的部分只计一次。
举个例子，两个矩形 (1,1,4,3) 和 (2,2,5,4)，单个面积都是 6，重叠部分是 (2,2,4,3) 这个面积 2 的小矩形，所以答案应该是 10，不是 12。这 10 怎么算出来，就是整个算法的核心问题。
这道题最恶心的点在于数据规模。n 最大是 1e5，坐标范围 0 到 1e9。这个范围意味着任何依赖坐标绝对值做枚举的思路都不可行，必须把问题抽象成事件流，只处理矩形边界上那些有限的“关键位置”。
1.2 为什么暴力做法顶不住
先看二维标记法。如果坐标范围只有 1000，完全可以直接开一个二维布尔数组，每个矩形覆盖的格子打上标记，最后数一遍多少个格子被点亮。可坐标是 1e9，别说二维数组，就算用哈希把离散网格存下来，一万个矩形产生的格子数量也能炸穿内存。
再看离散化加容斥。把 x 和 y 坐标分别离散化后，整个平面被切成最多 (2n)² 个小网格。对每个网格判断是否被某个矩形覆盖，复杂度至少是网格数乘矩形数，n 到 1e5 的时候就是 4e14 级别，根本算不完。
所以必须换思路。一个矩形虽然占了一块二维区域，但它的边界其实就是四条线段。如果沿着 x 轴放一条垂直的线从左往右扫，这条线在任意一个 x 位置都只会露出一段或几段 y 方向上的“被覆盖区间”。真正让这条扫描线的状态发生变化的，只有矩形的左右边界。那么整张平面的覆盖总面积，就可以拆成一段段“矩形条”面积之和。
2. 扫描线算法核心拆解
2.1 把矩形边界变成事件
每个矩形 (x1,y1,x2,y2)，可以拆成两条竖直扫描事件：
- 事件一：在 x = x1 处，y1 到 y2 这段区间进入覆盖状态，标记为 +1。
- 事件二：在 x = x2 处，y1 到 y2 这段区间退出覆盖状态，标记为 -1。
这样 n 个矩形就变成 2n 条事件线，每条事件线的结构是 (x, y1, y2, val)，其中 val 是 +1 或 -1。把所有事件线按 x 从小到大排序，我们只需要在 x 取这些事件线对应坐标的时刻，更新一下“当前 y 方向覆盖了多长”，其余任意两个相邻事件线之间的区域，覆盖状态完全不变。
为什么不需要扫描无限多个 x？因为两块相邻的竖边之间没有新的矩形进入或离开，所以 y 方向被覆盖的长度是一个常数。这个常数乘以两块竖边的水平距离，就是这一小条区域的面积。
2.2 面积为什么能这样累加
假设排序后的事件线横坐标依次是 x0, x1, ..., x2n-1。在 x_{i-1} 到 x_i 之间，y 方向被覆盖的并集长度记为 H，那么这一块的面积就是 (x_i - x_{i-1}) × H。
把所有这样的细条面积加起来，就是整个并集面积。这里的关键是 H 是并集长度，不是覆盖次数。两个矩形在同一段 y 区间上叠了两层，H 也只取一次长度，这样重叠部分天然不会重复计数。
用个生活化类比：想象你有一排竖直的彩色贴条，每个矩形是一张贴条在 x 方向的延伸范围。扫描线扫过去的时候，我们在每个 x 切片上只看“哪些 y 位置最外面有颜色”，把所有有颜色的段落长度加起来，乘以切片厚度。哪怕下面叠了十层，最外层能看到的颜色也只算一次。
2.3 一个手算的完整小模拟
我直接拿上面两个矩形做一次完整的手算，这样整个算法的数据流会很清楚。
矩形 A：x1=1, y1=1, x2=4, y2=3，事件为 (1,1,3,+1) 和 (4,1,3,-1)。
矩形 B：x1=2, y1=2, x2=5, y2=4，事件为 (2,2,4,+1) 和 (5,2,4,-1)。
把 4 条事件线按 x 排序，得到：
| x | y1 | y2 | val | 操作 |
|---|---|---|---|---|
| 1 | 1 | 3 | +1 | 覆盖 [1,3] |
| 2 | 2 | 4 | +1 | 覆盖 [2,4] |
| 4 | 1 | 3 | -1 | 取消覆盖 [1,3] |
| 5 | 2 | 4 | -1 | 取消覆盖 [2,4] |
扫描流程：
- 初始覆盖长度 H = 0。
- 处理第一条线 x=1，覆盖 [1,3]，更新后 H = 2。
- 处理第二条线 x=2。累计从 x=1 到 x=2 这一段的面积：(2-1) × 2 = 2。然后更新覆盖 [2,4]，此时整个 y 方向覆盖是 [1,3] 和 [2,4] 的并集 [1,4]，H = 3。
- 处理第三条线 x=4。累计从 x=2 到 x=4 的面积：(4-2) × 3 = 6，累计面积变成 8。然后取消覆盖 [1,3]，剩下覆盖 [2,4]，H = 2。
- 处理第四条线 x=5。累计从 x=4 到 x=5 的面积：(5-4) × 2 = 2，累计面积变成 10。然后取消覆盖 [2,4]，H = 0。
最终答案是 10，跟手动算的两个矩形并集面积完全一致。
注意第三步和第四步的顺序：先累加当前覆盖长度和当前 x 到上一 x 之间的面积，再处理当前这条事件线。这件事在后面写代码的时候非常关键，顺序错了整个累加就全乱套。
3. 线段树维护“当前覆盖总长度”
3.1 离散化后线段树管的是线段，不是点
扫描线每次更新操作，都是对 y 方向的一个区间执行整体覆盖或取消覆盖。y 坐标范围最大 1e9，不能直接建线段树，所以第一步要把所有矩形涉及到的 y 坐标收集起来，排序去重，得到一个离散化数组 ys。
这里最折磨人的是线段树节点到底代表什么。普通线段树每个叶子节点通常代表一个点，比如数组下标；但这道题里，一个叶子必须代表相邻两个离散化坐标之间的一小段区间。
举个例子，覆盖 [1,3] 和 [2,4]，如果线段树只维护离散点 1、2、3、4，那么点 1 被覆盖、点 2 被覆盖、点 3 被覆盖、点 4 被覆盖，看起来好像中间是连续覆盖的，但实际上 [1,2] 这段长度和 [2,3] 这段长度、[3,4] 这段长度都不是一回事。我们需要明确知道的是整段长度的并集，不是几个点的覆盖状态。用“点”当叶子天然会丢失区间内部的信息。
所以正确的做法是：线段树节点 [l, r] 表示离散化下标从 l 到 r 的所有端点之间组成的区间合集，叶子节点是满足 l + 1 == r 的节点，它对应真实坐标区间 [ys[l], ys[r]]。也就是说树上一共维护 ys.size() - 1 个最小的 y 方向单位区间。
3.2 cnt 和 len 的含义
线段树每个节点维护两个关键值：
- cnt：当前节点代表的整段区间被矩形完整覆盖的次数。
- len：当前节点代表的区间里，实际有覆盖的并集总长度。
每次更新传进来一个区间 [qyl, qyr] 和一个 val（+1 或 -1）。如果当前节点的区间被完全包含在更新区间内，直接把 cnt 加上 val，然后重新计算 len；否则就往左右子树递归，直到找到被完整覆盖的节点。
pushup（向上合并）的时候分三种情况：
- 当前节点 cnt > 0，说明整个节点区间都被覆盖了，len 直接等于 ys[r] - ys[l]。
- 当前节点 cnt == 0 且是叶子节点，说明这个最小单位区间没被覆盖，len = 0。
- 当前节点 cnt == 0 且不是叶子，说明这个区间没有被完整覆盖，但可能被子区间部分覆盖，len 等于左右子树 len 之和。
这样根节点的 len 永远表示整个 y 方向上被覆盖的并集总长度。扫描线在累加面积的时候，每次直接取 tr[1].len 就行。
3.3 为什么这里不需要 pushdown 懒标记
很多人第一次看到这套模板，最大的疑惑是：更新时明明只改了完整覆盖的节点，没有把 cnt 往下传给子节点，为什么不会出错？普通线段树区间加都要 pushdown，你这个扫描线怎么不 pushdown？
原因在于查询方式不一样。普通线段树需要查询任意区间的累加值，所以父节点的未下传标记会影响子区间的查询结果，必须在下一次触碰子区间的时候把标记推下去。但扫描线线段树从始至终只查询根节点，也就是整个 y 区间的总覆盖长度，不查任何一个子区间。
再看数据流的正确性。如果父节点 cnt > 0，说明整个区间都被覆盖，根节点的 len 一定是全长。这时候即使有人往里层子节点继续更新，根节点 len 也只取决于父节点自己的 cnt，不会被孩子影响。等到取消覆盖、父节点 cnt 减到 0 的时候，len 才会回退成左右子节点 len 之和。而子节点的 len 早就在之前的部分覆盖操作中更新过了，所以结果依然是准确的。
可以理解为这是一种“信息按需合并”的思路。父节点 cnt 为 0 的时候，子节点的信息是暴露的；父节点 cnt 大于 0 的时候，子节点的信息被整体盖住，算总长时只需要父节点自己的 cnt 就够。这就是不需要懒标记的根本原因。
4. 完整 AC 代码逐段拆解
4.1 扫描线事件与结构体定义
先定义事件结构体 Line。每个矩形产生两条 Line，一条入边一条出边。x 存扫描线的横坐标，y1、y2 是覆盖区间端点，val 表示加覆盖还是减覆盖。
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 100005; struct Line { ll x, y1, y2; int val; bool operator < (const Line& other) const { return x < other.x; } } line[N << 1]; vector<ll> ys;排序规则第一关键字是 x。同一 x 的多条线顺序无所谓，因为它们的水平距离是 0，不产生面积差。这一点后面会在易错点里再展开。
4.2 线段树的构建与核心更新逻辑
线段树直接用结构体数组实现，每个节点存离散化下标区间 [l, r]、覆盖次数 cnt、覆盖长度 len。
struct SegTree { struct Node { int l, r; int cnt; ll len; } tr[N << 3]; void build(int p, int l, int r) { tr[p].l = l; tr[p].r = r; tr[p].cnt = 0; tr[p].len = 0; if (l + 1 == r) return; // 叶子：只包含 ys[l] 到 ys[r] 这一小段 int mid = (l + r) >> 1; build(p << 1, l, mid); build(p << 1 | 1, mid, r); // 注意右儿子左边界是 mid，不是 mid + 1 } void pushup(int p) { if (tr[p].cnt > 0) { tr[p].len = ys[tr[p].r] - ys[tr[p].l]; } else if (tr[p].l + 1 == tr[p].r) { tr[p].len = 0; } else { tr[p].len = tr[p << 1].len + tr[p << 1 | 1].len; } } void update(int p, int ql, int qr, int val) { if (ql <= tr[p].l && tr[p].r <= qr) { tr[p].cnt += val; pushup(p); return; } int mid = (tr[p].l + tr[p].r) >> 1; if (ql < mid) update(p << 1, ql, qr, val); if (qr > mid) update(p << 1 | 1, ql, qr, val); pushup(p); } } seg;build 里的叶子判定 l + 1 == r 是这套模板的灵魂。左右儿子划分要特别注意：左儿子区间是 [l, mid]，右儿子区间是 [mid, r]。mid 这个下标在左右两个节点里都出现，但分别代表不同的相邻区间端点。如果写成 [l, mid] 和 [mid+1, r]，就会把 ys[mid] 和 ys[mid+1] 之间这段小区间漏掉，整个覆盖长度计算就会出错。
update 里的两个递归条件也是同样的道理。ql < mid 才递归左边，因为如果 ql == mid，更新区间 [ql, qr] 和左儿子区间 [l, mid] 只在端点 mid 相接，没有实际宽度。qr > mid 才递归右边，同理。这个细节不仔细想就会写成 ql <= mid 和 qr >= mid，虽然大多数数据跑不出差别，但严格意义上是错的，碰到边界情况会被卡。
4.3 主函数流程与答案累加
主函数的处理流程分成五步：读入矩形、生成事件、离散化 y 坐标、建树、扫描累加。
int main() { int n; scanf("%d", &n); for (int i = 0; i < n; i++) { ll x1, y1, x2, y2; scanf("%lld%lld%lld%lld", &x1, &y1, &x2, &y2); line[i] = {x1, y1, y2, 1}; line[i + n] = {x2, y1, y2, -1}; ys.push_back(y1); ys.push_back(y2); } sort(line, line + 2 * n); sort(ys.begin(), ys.end()); ys.erase(unique(ys.begin(), ys.end()), ys.end()); seg.build(1, 0, (int)ys.size() - 1); ll ans = 0; for (int i = 0; i < 2 * n; i++) { if (i > 0) ans += (line[i].x - line[i - 1].x) * seg.tr[1].len; int l = lower_bound(ys.begin(), ys.end(), line[i].y1) - ys.begin(); int r = lower_bound(ys.begin(), ys.end(), line[i].y2) - ys.begin(); seg.update(1, l, r, line[i].val); } printf("%lld\n", ans); return 0; }累加答案的时机很讲究：每次先算从上一个 x 到当前 x 之间的面积，再处理当前 x 上的事件。这样写最稳，因为第一条事件线之前没有面积差，i = 0 时自然跳过累加，只做第一次覆盖更新。之后每次事件线更新前，tr[1].len 恰好是前一个 x 区间上的覆盖高度。
lower_bound 查出来的 l 和 r 直接传给 update，注意这里 r 不需要减一。因为线段树节点维护的就是“端点下标到端点下标”的区间合集，传入 y2 的下标 r，实际会更新 [ys[l], ys[r]] 这一整段，天然包含所有最小单位区间。这个点跟普通点线段树完全不同，也是新手最容易写错的地方。
4.4 复杂度与空间估算
整个算法的时间复杂度是 O(n log n)：事件排序 O(n log n)，离散化排序去重 O(n log n)，总共 2n 次线段树更新，每次 O(log n)。坐标范围再大也无所谓，因为离散化后线段树的规模只跟矩形数量有关。
空间方面，线段树节点数组开 N << 3 属于非常宽裕的写法。实际上 4n 就够，因为叶子数量最多 2n - 1 个。我习惯多开一倍，纯粹是防止手误，竞赛场上内存溢出比浪费几 KB 严重得多。
5. 实战易错点与调试经验
5.1 更新区间的下标边界问题
这是扫描线模板翻车率最高的一步。前面说了，update 传入的是 y1 和 y2 离散化后的下标，而 r 就是 y2 的下标，不要减一。很多人学普通线段树学得太熟，下意识把“闭区间点更新”的习惯带进来，写成 update(1, l, r - 1, val)，结果答案总是偏小。
为什么不能减一？因为普通线段树叶子是点，区间 [l, r] 包含 r-l+1 个点；这题叶子是线段，区间 [l, r] 代表 ys[l] 到 ys[r] 之间连续的小段，一共 r-l 段，但端点下标就是 l 和 r。比如 ys = [1,3]，覆盖 y1=1 到 y2=3，调用 update 的时候 l = 0, r = 1，减一变成 [0,0] 就什么也更新不到了。我当初就是靠这个反例彻底记住的，写完之后可以自己造一组数据验证。
5.2 同 x 扫描线和排序顺序
事件排序只按 x 排，不需要第二关键字。原因很简单：同 x 的两条事件线之间宽度差是 0，不管它们内部顺序怎么交换，累加面积都不会变。但要注意累加和更新在同一个 x 上的先后顺序。
我推荐的扫描写法是在处理每条事件线之前，先累加答案。这样同 x 事件即使被 sort 分成前后两条，先累加的面积差为 0，再分别更新覆盖状态，所有同 x 事件处理完后，覆盖状态正确，面积也没有多算。如果你把累加放在更新之后，那就要额外判断同一 x 只累加一次，逻辑更绕，完全没有必要。
5.3 线段树数组大小和数据类型
离散化数组 ys 里最多 2n 个坐标，n 等于 1e5 时就是 2e5 个。线段树 build 的范围是 0 到 ys.size()-1，叶子数是 ys.size()-1。常规线段树开 4 倍节点数一定够，我自己习惯开 8 倍是为了省心，竞赛里不影响时间。
数据类型上，坐标虽然是整数，但答案是 1e14 级别的，必须用 long long。我见过很多人在 ans 上开 long long，却忘了 ys 是 vector ，线段树 len 也是 ll，结果中间那个乘积溢出了一整版负数。这个问题在检查代码时最容易漏，建议所有跟坐标、长度、答案相关的变量统一用 ll。
这里整理一份排查速查表：
| 常见错误 | 错误特征 | 正确做法 |
|---|---|---|
| update 传 r-1 | 答案偏小，重叠区域越大差越多 | 直接传 y2 的离散化下标 r |
| 叶子判定写成 l == r | 线段树无限递归或漏覆盖 | 叶子判定用 l + 1 == r |
| 右儿子边界写成 mid+1 | 覆盖长度少算相邻小段 | 右儿子左边界用 mid |
| ans 或 len 用了 int | 大样例输出负数或错误整数 | 全部用 long long |
| 累加和更新顺序反了 | 同一 x 处多算/少算面积 | 每条线先累加再更新 |
| build 范围写成 [0, m) | 端点下标错位 | 节点区间是 [0, m-1] |
5.4 一个值得注意的递归细节
update 递归条件的写法，网上有的版本是先把 mid 算出来，然后无脑对左右孩子都递归，靠开头的无交集判断剪枝：
if (ql <= tr[p].l && tr[p].r <= qr) ... if (qr <= tr[p].l || tr[p].r <= ql) return; mid = ... update(left); update(right);这种写法也能 AC，而且更通用，但多了一层无交集判断，常数略大。我给的条件写法 ql < mid 与 qr > mid 更贴合“端点区间”这套模型，本质上就是手动剪枝。两种都能用，但一定要理解为什么右儿子递归的起点是 mid 而不是 mid + 1，这是最容易让代码出 bug 的隐含约定。
6. 模板的迁移与更多应用场景
6.1 从面积并到周长并
学会面积并之后，矩形周长并就差一层窗户纸。周长由水平边长度和竖直边长度组成。
竖直方向的周长增量，其实是扫描线每移动一个 x，覆盖长度发生的变化量取绝对值，也就是 abs(newLen - oldLen)。因为覆盖变长或变短的部分都对应着新露出来的竖直边界。
水平方向的周长，则是每两个相邻 x 之间的距离乘 2，因为在扫描线经过的这段区间里，矩形的上下水平边各有一次贡献。做法就是每处理完一条事件线，记录这次的 len，和上一次的 len 做差取绝对值，累加进答案；同时把 (x[i] - x[i-1]) × 2 也累加进答案。一套代码能同时解决面积并和周长并，性价比非常高。
6.2 覆盖次数相关的变体
有时候题目会问“至少被 k 个矩形覆盖的总面积”。这种改造通常是把线段树节点里的 len 扩展成一个数组，比如 len[0..k]，分别表示被覆盖 0 次、1 次、2 次、更多次的长度。pushup 的时候根据 cnt 决定合并策略，比单纯面积并复杂一些，但整体框架仍然是扫描线加线段树。
还有一类问题要求删除某个矩形之后覆盖面积变化多少，这种往往需要维护前后缀覆盖长度来做离线处理，核心依然是扫描线这套事件模型。把模板吃透之后，这些变体都是在 cnt 和 len 的维护逻辑上叠加业务条件。
6.3 不想离散化的替代方案
如果不想写离散化，也可以用动态开点线段树直接覆盖 y 坐标范围。每次更新按真实坐标递归，节点没有使用过就临时创建。这种写法的优点是思路直观，不用处理 lower_bound，缺点是需要动态分配内存，递归深度在坐标 1e9 时大约是 30 层，常数偏大，内存控制也麻烦。
竞赛里应对这种模板题，我还是推荐离散化。它的思路固定，内存好估算，调试也简单。动态开点更适合在线维护、坐标范围不确定或者强制在线的场景，平时练习可以都写一遍，理解更深。
6.4 与二维差分离散化的对比
有些人会问，矩形面积并能不能用二维差分加离散化做。二维差分适合点覆盖、网格覆盖这类“格子”模型，每个矩形成增量打点在离散化的网格上，最后扫一遍统计。但矩形覆盖求的是连续实区间的并集长度，不是格子数量。二维差分在坐标离散化后，还是得枚举所有网格，而扫描线只用维护一维长度的变化，信息量完全不在一个级别。
这也是为什么扫描线一直是矩形面积并问题的标准解法。它把二维问题降维成一维区间维护问题，线段树负责高效维护这一维的覆盖状态，离散化负责把无穷多的坐标压缩成有限规模。三个技术组合起来，复杂度从不可做降到 O(n log n)，这就是这道模板题最大的价值。
我自己练这道题的时候，卡得最久的就是 l + 1 == r 这个叶子定义。后来找了两个重叠矩形，手工模拟了整整一遍 update 过程中每个节点的 cnt 和 len 变化，才真正想明白。建议你拿到代码先别急着提交，也拿一组小数据，把每个节点在每次事件后的状态写出来，跟代码跑的结果对一遍。这题理解到位的标志不是 AC，是你能看着某一行代码，说清楚它到底在维护哪个区间的哪一段信息。之后再去刷其它扫描线题目，你会发现骨架永远是那套，变的只是线段树节点里多放几个字段而已。
