1. 整体思路拆解扫描线、离散化和线段树是怎么凑到一起的先把这个标题拆开来看。扫描线、离散化、线段树、二分、卡常这五个词几乎是每一位打算法竞赛的选手都绕不开的坎。尤其是扫描线|离散化|seg二分这种组合一看就是那种矩形面积并、周长或者区间覆盖类的问题。如果你刷过POJ 1151或者HDU 1542这类经典题那你应该秒懂我在说什么如果你还没接触过那这篇文章就是给你准备的。先说扫描线和离散化之间的关系。扫描线算法的核心思想是把二维的几何问题转化成一维的区间维护问题——想象一根竖线从左往右扫过整个平面每碰到一个矩形的左边界就在某个数据结构里插入一条边碰到右边界就删除一条边。问题在于矩形的坐标可能是浮点数也可能是像1e9甚至1e18这样的大整数你总不能真的开一个1e9的数组去存每一个像素点吧这时候就需要离散化把所有的x坐标和y坐标收集起来排序、去重、映射成连续的整数下标然后再用线段树去维护这些被压缩后的区间。而线段树在扫描线里干的活本质上就是维护当前被覆盖的长度或者被覆盖的次数。但为什么还要再加上二分这就涉及到一些变形问题了。比如有的题不是让你算面积而是问你某个点被多少个矩形覆盖这时候你在离散化后的坐标值上做二分就能快速定位到对应的区间再在线段树里查这个点的覆盖次数。再比如有些题目要求找到第k个被覆盖的位置线段树上二分的经典操作就派上用场了。所以seg二分不是一个固定模板而是一种常见的组合套路具体怎么组合得看题目问什么。最后说卡常。扫描线加线段树裸写一套下来复杂度通常是O(n log n)看起来不大但如果你用的是C的set、map或者vector的erase操作常数可能大到你无法想象。尤其是坐标是double型的时候离散化如果写得不好TLE就是说一声的事。卡常这个词在圈子里很玄乎但它本质上是让你在正确性没问题之后把代码的执行速度再榨出几倍来——用快读、手写哈希、避免不必要的函数调用、把递归线段树改成非递归版本这些都是常见手段。这篇博文不打算只讲一个模板题而是带你完整走一遍扫描线离散化线段树二分的思路演进过程再把我自己调试这类题时踩过的坑、卡常的骚操作全部抖出来。无论你是刚学会线段树的萌新还是已经能稳过省选难度的老手这篇文章里应该都有你用得上的东西。2. 核心细节解析与实操要点2.1 扫描线的置换思想从插入删除到区间覆盖次数扫描线这个名字听起来高大上其实本质就是把动态变化的过程拆成一个个离散的事件。假设你有若干个矩形矩形的边都是平行于坐标轴的。我们用一个垂直于x轴的竖线去扫那么每个矩形都由两条竖边组成左边界触发加入操作右边界触发删除操作。我们把所有竖边的x坐标提出来排个序然后从左到右依次处理。这里有个关键点扫描线扫的是事件点不是连续区间。所以你做的是在这个x位置插入一条y方向的线段或者删除一条y方向的线段。而这根y方向的线段一定落在某个[y1, y2]区间里。你需要一个数据结构来记录在这个扫描位置上所有这些被插入且还未被删除的线段合并起来在y方向上的总长度是多少。这就是线段树的活。有一种特别反直觉的地方当你在某个x位置插入了一条线段它影响的是[x, 下一个事件点]之间的这段宽度而不是从x到无穷远。换句话说扫描线是离散地处理事件但面积是分段算出来的——每两个相邻事件点之间的宽度乘以当前被覆盖的y方向总长度累加起来就是总面积。这也是为什么你必须把所有x坐标和y坐标都收集起来做离散化只有离散化之后你才能在O(1)时间内算出每段的实际宽度和实际高度。如果你做的是矩形周长问题逻辑稍有变化——周长由水平边和垂直边分别贡献。水平边是每插入一条线段后覆盖长度的增量乘以2垂直边是相邻事件点的x差乘以当前覆盖段的数量。这就对线段树提出了更高的要求你不仅要维护覆盖长度还要维护覆盖段数。很多初学者在这里犯糊涂以为线段树只能存一个值其实存什么取决于题目想让你算什么。2.2 离散化的正确姿势坐标压缩不是无脑排序去重离散化就是把稀疏的大范围坐标映射到连续的小范围下标。比如y坐标分布是{-10000, 1, 2, 999999}排序去重后得到{-10000(0), 1(1), 2(2), 999999(3)}每个原始坐标就对应一个下标。这样线段树只需要开44的数组而不是41000000。但离散化有个很隐蔽的坑如果你做的是面积并并且采用的是区间端点离散化后直接存点的方式那么你算出来的面积会偏大因为中间的空隙也会被算进去。所以正确做法是把相邻坐标点之间的间隙也当作一个叶子节点也就是说你离散化出来的每个下标其实代表的是[y_i, y_{i1})这个半开区间然后线段树叶子存的是区间长度而不是点。如果你直接用点的下标去映射丢掉了实际的长度信息那你后面算覆盖长度的时候就只能返回1而不是真实的(y_{i1} - y_i)结果自然不对。另一个容易搞错的地方是去重和排序必须用unique函数做完之后再用lower_bound查询映射。如果你的题目给了m个y坐标离散化后数组大小是n那么线段树build的时候一定要建到n-1个叶子每个叶子代表两个相邻坐标点之间的区间。很多模板题里的线段树是建立在点上的因为做单点更新、区间查询正好合适但扫描线用的是区间更新所以思想上不要套错。再提醒一点如果坐标是浮点数排序去重之后用lower_bound查询没问题但是浮点数相等判断时要小心精度一般题目会保证输入精度在一个容差范围内否则你需要在离散化前做一次eps容差合并。2.3 seg二分不是所有二分都是lower_bound还有线段树上二分标题里的seg二分最容易理解的是离散化坐标后用二分查找定位某个点在线段树里的位置。这种是最基础的。你有一个点坐标xi它在离散化数组里的下标是id然后你去线段树里查这个位置被覆盖了几次。这其实和普通lower_bound没太大差别只是把二分结果直接喂给了线段树。更有意思的是线段树上二分这是一个高级技巧。比如有这样一个需求在当前扫描线上找出第k个被覆盖的位置。常规想法是二分答案猜一个位置查它前面的覆盖次数总和然后缩小区间。这样做复杂度是O(log n * log n)勉强能过。但如果你直接在树上做二分就能一步到位从根出发看左子树维护的覆盖次数是否大于等于k如果大于往左走否则减去左子树的覆盖次数再往右走。这样一次O(log n)就搞定了省掉了外层二分。另一个常见场景是在区间覆盖次数上做统计比如求所有被覆盖次数恰好为c的区间总长度。这时候线段树节点里除了维护覆盖长度外还需要维护各种覆盖次数的分布。如果你只会用普通线段树就得在每个节点开一个map或者vector然后合并两个儿子时要手动排序合并复杂度直接上一个log。这也是卡常的重灾区。所以seg二分本质上是让你学会当线段树节点需要分类统计时如何在合并时用二分来加速。分类统计是一个经典变形它的典型做法是每个节点维护覆盖次数为1的区间长度、为2的区间长度……合并时根据子节点的最小覆盖值来重算。这个过程没有二分但其实在你用二分去查找某个坐标落在哪个分类区间时二分就出现了。理解这一层你才算真正吃透这个组合。3. 实操过程与核心环节实现3.1 数据结构设计线段树节点需要存哪些值针对最经典的矩形面积并我给出一个我认为最干净、最常用的线段树结构。这个结构不是我发明的是圈里迭代了很多版之后沉淀下来的写法我建议你直接背下来然后理解它。每个节点需要维护两个值一个是cover表示这个区间被完整覆盖的次数另一个是len表示这个区间当前的实际覆盖长度。注意这里len不是简单的区间长度而是根据cover是否大于0来决定的。如果cover 0说明整个区间都被覆盖了len就等于这个区间对应的原始坐标长度否则len等于左右子节点的len之和。这个设计妙就妙在不需要懒惰标记因为扫描线更新的是区间覆盖次数更新方向和删除方向是对称的不需要下放标记。然后是离散化数组ys它保存所有y坐标排序去重后的值。线段树建树时每个叶子节点[l, l]代表的是ys[l]到ys[l1]这段区间。注意叶子节点的下标范围是0到n-2如果你开的是1-indexed那就得小心边界。扫描事件的结构体我习惯写成struct Event { double x, y1, y2; int tag; // 1表示左边界-1表示右边界 };然后对事件按x排序如果x相同按tag排序确保同一个x位置先加后删避免面积计算错误。3.2 完整代码流程从读入到输出一次跑通我直接给出一份可以AC的代码框架基于经典HDU 1542改的。这里的习惯是用C写因为算法竞赛的主流就是C。#include bits/stdc.h using namespace std; const int N 10005; double ys[N 1]; int n, m; struct Event { double x, y1, y2; int tag; } ev[N 1]; struct SegTree { int cover[N 3]; double len[N 3]; void init() { memset(cover, 0, sizeof(cover)); memset(len, 0, sizeof(len)); } void pushUp(int p, int l, int r) { if (cover[p] 0) { len[p] ys[r 1] - ys[l]; } else if (l r) { len[p] 0; } else { len[p] len[p 1] len[p 1 | 1]; } } void update(int p, int l, int r, int ql, int qr, int val) { if (ql l r qr) { cover[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); } } seg; int main() { // 读入矩形收集y坐标离散化 // 构建事件并排序 // 遍历事件累积面积 }具体到每个事件查询y1和y2在离散化数组里的下标id1和id2然后调用seg.update(1, 0, m - 2, id1, id2 - 1, ev[i].tag)。注意这里为什么要用id2 - 1因为我们叶子节点代表的是区间[id1, id2-1]这个区间覆盖了从ys[id1]到ys[id2]的整段连续区域而r1在pushUp里用来计算长度时正好对应ys[r1]所以下标要抠清楚。面积累加的逻辑是area (ev[i1].x - ev[i].x) * seg.len[1]。也就是每两个相邻事件之间宽度乘以上一轮事件处理完之后根节点的覆盖总长度。3.3 二分的接入点为什么需要二分以及怎么实现上面这个模板题没有明显的二分。但如果你遇到的是区间覆盖次数查询或者查找第k个覆盖点你就得在事件处理中插入二分。假设题目问坐标点(xi, yi)被多少个矩形覆盖。首先你要在xs数组里二分出xi对应的下标idx再在ys数组里二分出yi对应的下标idy。然后你只需要在扫描线扫到xi这个事件点的时候去线段树里查询idy这个位置被覆盖了几次。如果你提前把所有事件和查询都处理完就可以离线做把所有询问按x排序和扫描事件一起按x合并处理遇到询问就写答案。这里的核心就是二分定位没有任何高深的地方。至于查找第k个被覆盖点则要用线段树上二分。做法是让每个节点额外维护覆盖次数总和然后从根开始判断如果左子树的覆盖次数总和大于等于k递归左子树否则k减去左子树总和递归右子树。注意这里的覆盖次数总和不是len而是所有区间cover的总和或者根据题目定义的量。3.4 卡常技巧实战从IO到数据结构层层优化卡常不是一个华丽的技巧而是从每一个细小的环节里挤出来的性能。我按照最重要的顺序给你排个序。第一读入优化。如果你的题目输入量是10万级别以上用cin不关同步几乎必TLE。建议写个模板级的快读函数或者至少ios::sync_with_stdio(false); cin.tie(0);。我个人的习惯是直接手写readInt()和readDouble()用scanf也行但scanf的double读取也有开销手写大整数快读用指针会更稳。第二离散化去重不要用vectorsortunique一把梭吗可以但要注意unique返回的是迭代器别漏写m unique(ys, ys m) - ys;这种边界。我见过太多人在这里出错因为忘记更新新的m。第三递归改非递归段树。如果你用上面的递归update和pushUp每个事件更新是O(log n)但递归函数的调用开销在10^5级别事件下还能接受在10^6级别就完全扛不住。非递归线段树zkw线段树能省掉大半函数调用开销。简单做法是用数组模拟栈或者用zkw那种从底部更新往上推的方式。zkw版本尤其适合扫描线因为扫描线更新是区间更新可以在zkw上写带tag的区间更新但实现难度比递归版高一个档次。如果你是第一次学我建议先把递归版写对再考虑优化。第四用register和inline现代的编译器O2优化早就把这些做了你手动加inline反而可能干扰编译器。真正有效的卡常是减少访问次数和内存局部性。比如把Event结构体按照x排序后连续访问ys数组和线段树数组都开成静态全局数组避免vector的动态扩容和访问间接寻址。这些才是实打实的快。第五能用数组就别用vector能用int别用double。如果题目保证坐标是整数那离散化就全用int面积也可能超int但要开long long。如果你用double算面积精度问题还会出来。总之数据类型的转换能省就省。4. 常见问题与排查技巧实录4.1 覆盖次数出现负数或者面积不符合预期这是扫描线新手最容易遇到的错误。覆盖次数出现负数大多数情况是你的事件排序不对同一个x坐标处某条矩形的右边界tag-1竟然被处理在了左边界tag1之前。这会导致你先删除了一条还没插入的线段cover变成-1整个统计就崩了。处理办法排序事件时如果x相同就按tag从大到小排序即先加后删。这个细节在很多模板里被一笔带过但实际调试时你会发现自己怎么都想不通为什么面积是负的。另一个常见问题是离散化后线段树区间边界搞混导致覆盖的长度正好差了一条边。建议你手推一个小例子比如两个矩形一个在[0,2]一个在[1,3]你自己把所有事件和update区间走一遍就会明白id2 - 1的来历。4.2 用二分查找离散化下标时找不到值有时候你收集的坐标数组里并没有你要查的那个坐标。比如一个点刚好在矩形边界上你把它当坐标点插到离散化数组里但你查询的时候用的坐标系和离散化数组不一致。要避免这个问题最稳妥的方式是把所有可能出现在查询里的坐标全部收集进离散化数组。也就是说如果你需要二分查找某个xi那么你就应该先把所有矩形x边界和所有查询xi都放在一起排序去重。否则lower_bound一定会返回end()或者插入位置右端导致访问越界。如果你不想把所有查询坐标都参与离散化那就只能接受点或边界在某个区间内的容差判断但这种做法容易出锅我强烈不建议。4.3 线段树数组开小了导致段错误或答案诡异扫描线线段树通常需要4倍区间长度。这里区间长度是离散化后的点数减1也就是最多2*n-1。如果你开了全局静态数组建议直接开成(N 3)不要省。N是矩形数量的两倍因为每个矩形产生两条竖边每个竖边的y端点各有两个。我见过有人只开4倍结果在边界数据上疯狂RE这问题排查起来还不好定位因为段错误不一定在首次访问时出现。如果你是新手建议把线段树建立一个build函数把所有叶子节点和内部节点的len初始化成0cover初始化成0。不要依赖全局变量默认为0因为多组测试数据时不清空会出玄学错误。4.4 二分死循环求上界和下界搞混如果你在做线段树上二分最典型的错误是k的边界没处理好。比如你要找第k个被覆盖的点但整个扫描线上被覆盖的点的总数小于k这时候你的查询函数会自动返回最右端或者根节点你必须在外层先判断总数是否大于等于k。第二个坑是当覆盖次数为0的区间也参与查询时你不能只看当前节点cover是否大于0还要看左子树合不合适。若左子树覆盖次数之和小于k你减去后再进右子树最后一步一定是在叶子节点上判断。调试二分的秘诀就是输出中间过程。很多人写线段树上二分时不敢输出其实你只需要在每个递归入口打印当前节点的区间和k两步就能定位出问题。5. 从模板题到变式题扫描线思维的扩展5.1 矩形周长并需要在节点里额外维护段数如果你只会面积并那周长并对你来说就是一个难度跃升。周长并除了要维护覆盖长度len还要维护当前被覆盖的连续段数num。为什么需要段数因为垂直方向的周长增量等于相邻扫描线之间的x差乘以覆盖段数。你可以想象一根线被切成几段段与段之间的间隔就贡献了额外长度。实现上每个节点除了cover和len还要维护该区间从左右端点是否能接上左右段。也就是lc和rc两个bool值表示该节点区间最左边位置是否被覆盖、最右边位置是否被覆盖。合并时num left.num right.num - (left.rc right.lc ? 1 : 0)。这个逻辑很自然但第一次写的人会觉得复杂。我建议你在理解了面积并之后再动手写周长并写的时候务必先用样例手推一遍。5.2 二维平面里的“扫描线二分”还能干更多事扫描线并不只限矩形。它本质上就是一维区间维护一维顺序扫描的套路。所以你可以把它用在很多奇怪的问题上比如平面上有N个圆求这些圆覆盖的总面积需要分段逼近又比如给你一堆线段求这些线段在某个扫描线方向上的投影长度。核心永远是把二维裁剪成一维操作。当你熟练掌握离散化线段树二分这套组合后很多题目你第一反应就是能不能扫描线。我见过不少选手一看到多次矩形覆盖求区域就直接想扫描线但没意识到如果矩形的数量巨大而且每次插入删除的区间很窄那线段树的常数可能会吃紧这时候就要考虑用树状数组差分替代线段树。选型的时候你要看清题目是区间修改区间查询还是区间修改单点查询。后者完全不需要线段树树状数组加差分就够而且常数小得多这是很高明的卡常思路。5.3 卡常的极限从O(n log n)到更小的常数有人说算法竞赛就是比谁常数小这句话有点极端但也有道理。同样一个扫描线有的人能跑进1秒有的人超时到2.5倍时限。差距主要不在算法复杂度上而在你使用的数据结构细节和输入输出手段。比如线段树的build是完全没必要的你可以直接初始化数组全0然后把len数组按区间长度初始化这能省一次递归遍历再比如你更新的时候如果传参过多可以用函数内联或者写成全局指针减少栈帧开销。另一个卡常大招是只在根节点维护答案。因为扫描线每次更新完后你只需要根节点的len那你可以只对根节点做pushUp不必每个中间节点都更新。类似地如果你的update操作区间总是更新到整个根节点的子集那么在一次更新中你最多只需要更新一条路径上的节点。这通常靠懒惰标记就能做到。我个人的习惯是先写出朴素但正确的递归版然后跑一次极限数据看时间。如果超了再一项一项优化。不要一上来就写zkw因为zkw的bug一旦出现调试成本极高。6. 调试与验证手段如何快速确认你的扫描线写对了6.1 用Python或者暴力程序对拍无论你用什么语言写正解我都强烈建议你写一个暴力程序来对拍。扫描线的正确性验证其实很简单因为坐标范围是离散的整数时你可以直接用二维数组标记每个格子然后统计被覆盖的格子数。如果矩形数量小、坐标范围小这种暴力就能当标准答案。对拍脚本的写法很固定生成若干组随机数据分别运行暴力程序和正解程序逐行对比输出。我一般用Python写个脚本循环10000次每次数据量控制在矩形数量50以内坐标范围在0到20以内。这样暴力程序的循环不会爆炸。一旦对拍找到反例就用debug输出定位。这个方法比你在OJ上反复提交然后看WA靠谱得多。6.2 单步调试的核心观察len数组和cover数组的变化如果你是新手不会写对拍脚本那你在本地调试时就要学会看线段树的内部状态。我建议把update函数里面加一个条件编译当debug宏开启时每次更新后打印节点区间和cover值。但别打印太多否则刷屏。我一般只打印和根节点相关的信息更新完某个事件后根节点的len是多少。因为你最终面积就是遍历所有事件时根节点len的积分。还有一种常见的错误是离散化后坐标原点问题。比如用0-indexed还是1-indexed这直接影响ys[r1]的下标。如果里面对不齐你会发现len始终是0或者总是多算一段。这时候你就在pushUp里打印l、r、ys[l]、ys[r1]一眼就能看出问题。6.3 经验总结这套模板的适用范围和变体写这篇文章并不是让你死记硬背一个模板而是让你理解这套思想可以迁移到哪里。扫描线最经典的两个应用是面积并和周长并但除此之外矩形覆盖点查询、最大矩形交集高度、区间覆盖总长度等题目都可以套用同一套代码骨架。你只需要修改线段树节点的统计信息和update的维护逻辑。如果你刷题量不够我建议你先把HDU 1542、POJ 1151、POJ 1177这三道题刷透。它们分别对应面积并、矩形覆盖性、周长并。这三道题刷完扫描线基础基本就扎实了。然后再去找区间覆盖第k大点的题练线段树上二分。等你这套组合拳打熟了再遇到标题里带离散化的题你心里就该有底了。7. 写在最后关于卡常和坚持我在实际比赛里吃过不少卡常的亏。有一次省赛题思路完全正确复杂度理论上是O(n log n)但就是TLE。那时候我还没有掌握非递归线段树也没有把读入优化做到极致。后来我把所有vector换成静态数组把递归线段树改成带懒惰标记的zkw版本时间直接砍掉三分之二。从那以后我养成了一个习惯每次写完扫描线类题目都会自己跑一组极限随机数据看一下运行时间再用perf的思维粗略估算哪部分耗时最多。这不是强迫症而是对题目的尊重。踩过几次坑之后你会发现扫面线这套算法最难的其实不是线段树怎么写而是你愿不愿意把每个细节抠明白——从离散化下标到区间覆盖长度的推演再到二分查找时细节的谨慎。这篇文章里写的每一条注意事项都是我亲手在OJ上“WA到天亮”换来的。如果你按照这个思路去写题应该能少走很多弯路。最后再分享一个小技巧如果你在比赛现场遇到扫描线时紧张到写不完可以直接背一个面积并的模板然后在这个基础上改。因为80%的扫描线题目都是在面积并模板上做微调比如把len改成你需要维护的量或者加上查询函数。把最经典的模板背熟真的能救命。