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_{i+1})这个半开区间，然后线段树叶子存的是区间长度，而不是点。如果你直接用点的下标去映射，丢掉了实际的长度信息，那你后面算覆盖长度的时候就只能返回1而不是真实的(y_{i+1} - 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[l+1]这段区间。注意叶子节点的下标范围是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]的整段连续区域，而r+1在pushUp里用来计算长度时正好对应ys[r+1]，所以下标要抠清楚。
面积累加的逻辑是：area += (ev[i+1].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读取也有开销，手写大整数快读用指针会更稳。
第二，离散化去重不要用vector+sort+unique一把梭吗？可以，但要注意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）竟然被处理在了左边界（tag=1）之前。这会导致你先删除了一条还没插入的线段，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初始化成0，cover初始化成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[r+1]的下标。如果里面对不齐，你会发现len始终是0或者总是多算一段。这时候你就在pushUp里打印l、r、ys[l]、ys[r+1]，一眼就能看出问题。
6.3 经验总结：这套模板的适用范围和变体
写这篇文章并不是让你死记硬背一个模板，而是让你理解这套思想可以迁移到哪里。扫描线最经典的两个应用是面积并和周长并，但除此之外，"矩形覆盖点查询"、"最大矩形交集高度"、"区间覆盖总长度"等题目都可以套用同一套代码骨架。你只需要修改线段树节点的统计信息和update的维护逻辑。
如果你刷题量不够，我建议你先把HDU 1542、POJ 1151、POJ 1177这三道题刷透。它们分别对应面积并、矩形覆盖性、周长并。这三道题刷完，扫描线基础基本就扎实了。然后再去找"区间覆盖第k大点"的题，练线段树上二分。等你这套组合拳打熟了，再遇到标题里带"离散化"的题，你心里就该有底了。
7. 写在最后：关于卡常和坚持
我在实际比赛里吃过不少卡常的亏。有一次省赛题，思路完全正确，复杂度理论上是O(n log n)，但就是TLE。那时候我还没有掌握非递归线段树，也没有把读入优化做到极致。后来我把所有vector换成静态数组，把递归线段树改成带懒惰标记的zkw版本，时间直接砍掉三分之二。从那以后我养成了一个习惯：每次写完扫描线类题目，都会自己跑一组极限随机数据，看一下运行时间，再用perf的思维粗略估算哪部分耗时最多。这不是强迫症，而是对题目的尊重。
踩过几次坑之后你会发现，扫面线这套算法最难的其实不是线段树怎么写，而是你愿不愿意把每个细节抠明白——从离散化下标到区间覆盖长度的推演，再到二分查找时细节的谨慎。这篇文章里写的每一条注意事项，都是我亲手在OJ上“WA到天亮”换来的。如果你按照这个思路去写题，应该能少走很多弯路。
最后再分享一个小技巧：如果你在比赛现场遇到扫描线时紧张到写不完，可以直接背一个面积并的模板，然后在这个基础上改。因为80%的扫描线题目都是在面积并模板上做微调，比如把len改成你需要维护的量，或者加上查询函数。把最经典的模板背熟，真的能救命。
