扫描线 离散化 线段树 二分 卡常这几个词垒在一起懂行的老哥嘴角已经开始上扬了今天又要被几何题折磨。我刷了这么多年 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[i1] 这一段称为区间编号 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; // op1 进入, 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[r1] - 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[i1]]。所以线段树的节点区间是 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 会大于 Rupdate 直接跳过物理面积是零安全起见也不会崩。这种退化 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 清零。这个细节我在一次 n1e5 的多 case 题里实测过能差出几倍的运行时间。4.4 卡常的次序先找算法瓶颈再动手我见过有人把代码从 cin 改成 fread 后洋洋得意结果 TLE 依旧。后来才发现瓶颈根本不在读入而是事件排序的比较函数里不小心写了慢操作或者 lower_bound 反复调用太多次。所以我给卡常定的第一原则先判断这道题是 IO 密集还是计算密集再决定先优化哪一块。n 只有 1e5 时读入和排序都不是瓶颈真正的大头是线段树递归深度n 到 1e6 时优先查离散化映射的重复计算和数组清空。顺序搞反越卡越废。5. 常见问题与排查技巧这些坑我基本都踩过5.1 高频 bug 速查表下面这个表覆盖了我做扫描线题时遇到的大部分错误。写代码前扫一眼排错时对号入座能省很多时间。现象可能原因修法面积算大了update 的右边界没有减一导致多覆盖了一个区间段记住公式区间编号 左端点下标到右端点下标减一答案莫名其妙变成负数ans 或 segLen 用了 int全部换 long long坐标 1e9 时长度很容易溢出同一 x 处多个矩形的覆盖状态不对事件排序时第二关键字 op 没有降序cmp 里加一句 return a.op b.op明明有覆盖segLen[1] 却是 0pushup 的判断顺序错了顺序必须是 cnt0 优先其次叶子最后再用子节点拼接多组 case 第一组对第二组错totE 或 totX 没归零数组残留旧数据每组开头重置 totE、totX按实际用到的范围清零数组update 递归越界或死循环建树边界和 xs 下标不匹配检查线段树节点管辖的是区间编号 1..m-1不是坐标点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 语义、事件排序的稳定性、卡常的优先级任何一个地方模糊都会在数据最刁钻的时候打脸。先把这套标准模型吃透再去看变种题你会发现大部分题目无非是在这几件事上做一些加减法而已。