刷题刷到一定程度几乎绕不开 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 一个手算的完整小模拟我直接拿上面两个矩形做一次完整的手算这样整个算法的数据流会很清楚。矩形 Ax11, y11, x24, y23事件为 (1,1,3,1) 和 (4,1,3,-1)。矩形 Bx12, y12, x25, y24事件为 (2,2,4,1) 和 (5,2,4,-1)。把 4 条事件线按 x 排序得到xy1y2val操作1131覆盖 [1,3]2241覆盖 [2,4]413-1取消覆盖 [1,3]524-1取消覆盖 [2,4]扫描流程初始覆盖长度 H 0。处理第一条线 x1覆盖 [1,3]更新后 H 2。处理第二条线 x2。累计从 x1 到 x2 这一段的面积(2-1) × 2 2。然后更新覆盖 [2,4]此时整个 y 方向覆盖是 [1,3] 和 [2,4] 的并集 [1,4]H 3。处理第三条线 x4。累计从 x2 到 x4 的面积(4-2) × 3 6累计面积变成 8。然后取消覆盖 [1,3]剩下覆盖 [2,4]H 2。处理第四条线 x5。累计从 x4 到 x5 的面积(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] 和一个 val1 或 -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]; vectorll 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] 和 [mid1, r]就会把 ys[mid] 和 ys[mid1] 之间这段小区间漏掉整个覆盖长度计算就会出错。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-l1 个点这题叶子是线段区间 [l, r] 代表 ys[l] 到 ys[r] 之间连续的小段一共 r-l 段但端点下标就是 l 和 r。比如 ys [1,3]覆盖 y11 到 y23调用 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右儿子边界写成 mid1覆盖长度少算相邻小段右儿子左边界用 midans 或 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是你能看着某一行代码说清楚它到底在维护哪个区间的哪一段信息。之后再去刷其它扫描线题目你会发现骨架永远是那套变的只是线段树节点里多放几个字段而已。