ACM圈子里的老朋友应该都认得这个组合：扫描线、离散化、线段树、二分、卡常。五样东西单独拎出来哪个都不算冷门，但凑在一道题里，就能把一大半人按在地上摩擦。我去年秋天在OJ上重刷那道经典矩形面积并的时候，就是从“这题我闭着眼都能写”到“跑了一下午TLE”再到“终于过了”的状态，整个过程走完，才发现标题里这串关键词其实是环环相扣的：坐标范围大到没法直接建树，所以要离散化；扫描线按高度推进，每次要改一整段区间，所以要线段树；而离散化后的坐标和二分定位、卡常优化又死死绑在一起，少一个都过不了。
这篇东西我不想讲什么高大上的理论，就把我实际调试和重写过程中摸到的东西捋一遍，尤其是那些代码里不容易看出来的坑和优化选择。适合刚学完线段树、正准备挑战面积并/周长并这类题的人，也适合那些已经会写“裸扫描线”但总在数据加强版上吃TLE的老手。
1. 坐标压缩这张“地图”，为什么不是简单排序去重就完事
1.1 坐标轴的“数值密度”问题
先搞清楚我们到底在急什么。假设矩形数量 n 是 1e5，每个矩形的 x1、x2 范围在 [0, 1e9] 之间，你想直接在 x 轴上开线段树？那就得建 1e9 个叶子节点，不管用数组还是动态开点，空间和时间都直接爆炸。这个道理谁都知道，但“离散化”三个字具体落地的时候，很多人下意识以为就是“排序加去重”。
排序去重确实没错，但真正决定线段树形态的，是你要维护的“单位区间”到底是什么。拿矩形面积并来说，扫描线按 y 从下往上扫，每次遇到一条水平边，就把它对应的 x 方向区间 [x1, x2] 的覆盖次数加一或减一，然后查一下当前整个 x 方向上被覆盖的总长度。这个“区间”覆盖的边界，在离散化之后落到的根本不是某个坐标点，而是两个相邻离散点之间的一小段。
我举个例子。矩形 A 的 x 范围是 [1, 3]，矩形 B 的 x 范围是 [3, 5]。离散化数组是 {1, 3, 5}，共 3 个点，能形成 2 个相邻段：[1,3] 和 [3,5]。如果线段树叶子维护的是“点”3 是否被覆盖，那你会遇到一个经典问题：两个矩形在 x=3 这条边界上的覆盖次数会不会被算重？答案会。因为矩形 A 覆盖到 3，矩形 B 也从 3 开始覆盖，点 3 的覆盖次数会变成 2，但其实两个矩形的面积相交部分只是一条竖线，面积贡献是 0，这本不该算重。
正确的做法是让线段树的叶子维护“相邻两个离散点之间的半开半闭区间”，比如维护 [1,3) 和 [3,5)。这样矩形 A 覆盖第一段，矩形 B 覆盖第二段，没有任何一段被重复覆盖。等你把 [x1, x2] 映射到离散化下标时，用的其实是 [l, r-1] 这个半开区间。这个“为什么是 [l, r-1]”是离散化做对的一半关键，很多人卡了半天，就是因为在叶子定义上没想明白。
1.2 三步定位法：排序、去重、二分下标
具体写的时候，离散化可以固定成一套三步走，不要每次临场发挥。
第一步，把所有矩形的 x1 和 x2 原封不动地丢进一个 vector。第二步，sort 之后 unique，得到 xs 数组，长度记为 m。第三步，每条边在用的时候，用 lower_bound 在 xs 里查到 x1 对应下标 l，x2 对应下标 r，然后让线段树去更新区间 [l, r-1]。
vector<double> xs; for (int i = 0; i < n; ++i) { xs.push_back(rect[i].x1); xs.push_back(rect[i].x2); } sort(xs.begin(), xs.end()); xs.erase(unique(xs.begin(), xs.end()), xs.end()); int l = lower_bound(xs.begin(), xs.end(), rect[i].x1) - xs.begin(); int r = lower_bound(xs.begin(), xs.end(), rect[i].x2) - xs.begin(); // update [l, r-1]如果坐标是整数，这套写法可以直接跑。但坐标是浮点数时，unique 的等号判断就要小心。编译器对 double 的 == 是基于二进制表示的，同一道题里如果输入恰好是 1.0 和 1.00 而类型都是 double，那它们二进制一样，== 没问题；但如果一个坐标是 0.1 + 0.2 算出来的 0.3，另一个是直接输进来的 0.3，那这俩 double 不完全相等，unique 去重不去重，lower_bound 也可能查不到。实际比赛里要是有这种输入，建议把所有坐标读进来统一处理，别边算边插入，或者直接用 long long 存“坐标乘以某个缩放系数”后的整数。
1.3 离散化数组索引从 0 还是从 1，真的会影响后面二分
很多人写线段树习惯了 1 号根节点、左儿子 2u、右儿子 2u+1，于是顺手把离散化后的下标也改成从 1 开始。这没问题，但要记住：线段树里维护的是“段”，不是“点”。假设离散化后有 m 个坐标点，那线段树的叶子应该对应 m-1 个段，索引从 0 到 m-2，对应段 [xs[0], xs[1])、[xs[1], xs[2])……如果你强行让叶子从 1 开始，就得写 idx+1，很容易绕晕。
我个人的习惯是离散化数组下标从 0 开始，线段树节点存段编号，也就是 0 到 m-2。这样在 update 时传 [l, r-1]，边界计算少很多 bug。如果你已经习惯从 1 开始，也不是不行，只是在涉及“r-1”和“叶子个数是 m-1 不是 m”这两个点时，要反复和自己确认三遍。
提示：离散化后“点数 m”和“段数 m-1”的区别，是扫描线里最容易被忽略的边界来源。写线段树 build 时，如果左右端点写成 0 到 m 而不是 0 到 m-2，你的长度查询一定会多算或者越界。
2. 线段树在扫描线里维护的不是区间和，而是“覆盖次数和有效长度”
2.1 两个成员变量 cnt 和 len，作用完全不同
很多学线段树的人第一个写的是区间和、区间最大值，脑子里根深蒂固地觉得“节点存的值就是查询要的答案”。但扫描线里的线段树，核心变量有两个，而且关系微妙。
一个是 cnt，表示当前节点对应的这一段 x 范围，被多少个矩形完整覆盖。注意是“矩形覆盖次数”，不是“覆盖长度”。另一个是 len，表示当前这一段在覆盖次数 > 0 的情况下，实际贡献给总面积的有效长度是多少。
这两个值的关系不是简单的叠加。父节点的 len，不能由子节点的 len 直接相加，得先看父节点自己的 cnt。如果父节点 cnt 大于 0，说明整段都被覆盖了，len 直接等于这段对应的原始 x 长度，也就是 xs[r+1] - xs[l]。如果父节点 cnt 等于 0，说明父节点这一段没有整体覆盖，那 len 就只能由左右子节点的 len 合并上来。
void pushUp(int u, int l, int r) { if (cnt[u]) { len[u] = xs[r + 1] - xs[l]; } else if (l == r) { len[u] = 0; } else { len[u] = len[u << 1] + len[u << 1 | 1]; } }这里面的逻辑递进是：先看自己全被盖住，再看孩子有没有盖住，最后才看两边拼起来。很多人把 cnt 和 len 当成同一个东西，或者只用一个变量去模拟覆盖，就会出现在矩形相互嵌套时，覆盖次数减到 0 但实际长度还有残留，或者覆盖次数大于 0 但长度反而为 0 的诡异状态。
2.2 不需要懒标记的更新，是扫描线最舒服的地方
以前写区间加、区间求和时，线段树一定会配 lazy tag，否则更新复杂度退化回 O(n) 没法看。但扫描线的更新有个特殊性质：每次操作都是“把某个区间的 cnt 加一或减一”，而且加和减的操作在扫描过程中是成对出现的。这意味着我们可以不给它配 lazy，直接在节点上把 cnt 加上 delta，然后 pushUp 把 len 刷新就完了。
为什么能这样？因为 pushUp 的公式里，只要 cnt[u] 大于 0，len[u] 就直接等于整段长度，根本不管子树内部被覆盖成什么样。一个矩形进来，覆盖次数从 0 变成 1，那整段长度都算上；两个矩形叠着，覆盖次数从 1 变成 2，长度不变；其中一个矩形扫过去了，覆盖次数从 2 变成 1，长度还是整段；等最后一个也走了，覆盖次数从 1 变成 0，这时候 pushUp 才会去看子节点。整个过程里，我们从来没有“往下层节点精确修改”的需求，只要在区间边界处把整体覆盖次数累加好，len 的推导永远只需要看当前节点的 cnt 和孩子节点的 len。所以不需要 lazy，更新就是 O(log n) 的区间 cnt 修改加一路 pushUp。
这个设计我第一次接触时也觉得神奇，但它背后其实是“覆盖次数具有单调可叠加性”：一加一减不会产生需要子树内部分布信息的查询需求。理解这一点，后面遇到矩形周长并、以及二维平面上更复杂的覆盖问题，才能知道什么时候该上 lazy，什么时候不该上。
2.3 线段树数组该开多大，别拍脑袋开个 4 倍
常规模板里线段树开 4 倍节点，是基于 n 个点、区间完全覆盖思想的一个安全上界。但扫描线里叶子节点代表的是“段”，段的数量是 m-1，如果你把 m-1 当 n，开 4 倍空间，理论上也够。不过我一直习惯开 8 倍，原因有俩。
第一个原因是，有些写法会顺手在叶子节点上访问 xs[r+1]，如果 r 已经是 m-2 的段编号，r+1 就是 m-1，下标不越界；但如果你错误地把段数当成 m，或者在 build 时把区间端点写成 0 到 m，访问 xs[r+1] 就会越过数组末尾。空间开大一点，至少能把这种越界变成“稀奇古怪的答案”而不是“直接段错误”，更容易定位。
第二个原因是，部分题目不止一维扫描线，可能在二维线段树或者动态开点和静态数组之间切换，8 倍空间能避免递归过程中因边界写错而产生的越界风险。我自己有段时间为了省内存开 4 倍，结果在某道数据范围 1e5 的周长并题上连续 Re 了三发，换成 8 倍立刻过。虽然从理论上说 4 倍应该够，但竞赛里“空间换安心”是值得的，尤其是代码调试时间远贵于那几 MB 内存。
3. 二分在扫描线里的三种存在方式
3.1 最基础的：离散化坐标到段下标的二分转换
这是每个人都会写的那个 lower_bound。它的作用是把原始坐标 x 映射到离散化数组中的下标，然后才能去 update 线段树。这个二分本身没什么技术含量，但它是扫描线的“咽喉”：每个矩形两条竖边，每条边都要二分两次才能拿到 [l, r]，一次是 x1，一次是 x2，总操作次数是 2n。在 n 到 1e5 的时候这不算事，但如果你在一个循环里对每条边多次二分，常数就会悄悄膨胀。后面卡常部分我会重点说。
有个小技巧是，如果你的矩形的 x 集合在整个输入过程中都不会变化，可以在读入所有矩形后，一次性把每个矩形的 x1 和 x2 都映射成离散化下标存起来，之后扫描边的时候直接取下标，不要再对原始坐标反复二分。这样能把 2n 次 lower_bound 压缩成建图阶段的 2n 次 lower_bound，后续所有操作都变成纯整数比较，既省时间又减少出错可能。
3.2 线段树上二分：动态查找“当前第一个未被覆盖的位置”
扫描线本身不一定需要线段树上二分，但很多变种题需要。最典型的是“矩形面积并的补集”或者说“最少添加多少矩形才能覆盖某个区域”这类题，需要你不断地找当前扫描线上第一个覆盖次数为 0 的空白段。
如果你维护了 cnt 数组，那“第一个 cnt == 0 的位置”可以这样找：从根节点开始，看左儿子的 len 是否小于它对应的完整长度。如果左儿子还有空白，向左走；否则向右走。这就是一次线段树上的二分，复杂度 O(log m)，比“从左往右扫所有段”快很多。
int queryFirstZero(int u, int l, int r) { if (l == r) return l; int mid = (l + r) >> 1; if (len[u << 1] < xs[mid + 1] - xs[l]) { return queryFirstZero(u << 1, l, mid); } else { return queryFirstZero(u << 1 | 1, mid + 1, r); } }这种树内二分和普通数组二分最大的区别是：数组二分要求数据有序，而且你要猜答案的下标范围；线段树二分不需要猜，直接从根节点根据左右孩子的信息判断方向，本质上是在一棵天然的二叉搜索树上做路径查找，每一步决策都有明确依据。这个技巧在“求第 k 个覆盖段”“找最左空白区间”等问题里也通用。
3.3 二分套线段树 vs 线段树上二分，别搞混
很多加入二分答案的题，是“二分答案 + 线段树 check”的结构，复杂度是 O(logV * logn)。但如果你能用线段树直接在结构上二分，就不要再套一层二分答案，直接把那层 log 去掉。
我见过很多人在做“覆盖长度大于等于某个值的最短前缀”这类题时，先二分长度，再对每个 mid 建一棵线段树或者跑一次扫描线 check，时间复杂度直接多一个 log。其实如果你扫描线已经在维护 len 数组，完全可以在线段树上直接找“前缀和第一次达到 target 的段”（做法是先看左儿子 len 贡献，不够再向右），这样一次查询 O(log m)，整体复杂度就漂亮很多。
这里提醒一句：线段树上做“前缀和二分”，节点维护的必须是该段覆盖长度的累加值，而不是某种“是否覆盖”的布尔值。否则你没法判断向左还是向右。扫描线的 len 天然满足这个需求，所以你要是觉得自己扫描线题写得慢，多半是没有把“长度累加”和“二分查找”这两个能力组合起来用。
4. 卡常实录：不是算法不够好，是常数在拆台
4.1 读入输出优化，别省这几行
扫描线题通常输入量大，n 到 1e5 时，边数是 2e5，每条边四个坐标，轻则几十万个数，重则上百万。用 cin 不开同步，卡你几百毫秒轻轻松松。我的习惯是比赛环境直接用 ios::sync_with_stdio(false); cin.tie(nullptr);，如果是多组数据反复输入，就直接手写一个 fread 快读。
这里有个反直觉的地方：算法复杂度明明从 O(n^2) 优化到 O(n log n) 了，输入反而成了瓶颈。真不是开玩笑，我有一次在线段树逻辑完全一致的情况下，仅仅把 cin 换成 fread 快读，时间从 1900ms 压到 900ms。这还是在 O(n log n) 的题里。所以不要觉得快读是老古董，扫描线这种每个矩形要拆两条边、每条边又要做一次区间更新的题，读写操作的总量很可观。
4.2 结构体布局和 vector 预留，常被人无视
扫描线里最常见的边结构体是 {double x1, x2; double y; int delta;}。看起来只有四个成员，但如果你把 y 和 delta 放在 x1、x2 前面，排序时会反复比较 y，而 double 比较本身比 int 慢，所以能让 delta 这种 int 先排会稍微快一点。不过更关键的是，如果一组数据里矩形的数量已知，你应该提前给边的 vector reserve(2 * n)，避免中途扩容搬移元素。扩容是 O(n) 的内存拷贝，一次两次不觉得，但多组数据累计下来，时间就花了。
我实测过，同样是 1e5 矩形，reserve 之后整体耗时能省 5% 到 10%。这个比例不大，但在某些时限卡的变态的题里，5% 就是生与死的区别。另一个隐蔽点是，结构体里的 double 成员如果排布过于分散，sort 的时候缓存局部性差，比较成本也会上升。尽量把排序关键字放最前面，让 sort 的 compare 函数只比较前几个字节就能决出大小，这样省下的不只是 compare 调用，还有内存读取时间。
4.3 递归线段树的递归开销，可以这样压
扫描线的 update 是区间更新，递归深度是 log m 级别，一次更新大概访问 4log 个节点。n 到 1e5 时有 2e5 次 update，总节点访问量大概是 2e5 * 4 * 17 约 1360 万次。如果是递归函数，每次调用都有栈帧和参数传递，这个开销在某些老旧评测机上会很扎眼。
最常用的优化是把线段树写成非递归版，也就是 zkw 线段树。它的核心是自底向上更新，区间覆盖和 pushUp 都用循环完成，常数比递归版小很多。但 zkw 线段树对“维护 cnt 和 len”这套逻辑有点别扭，因为它的形态更适合区间和、区间最值这种“修改可以直接在叶子上做，然后向祖先累加”的场景。扫描线这种依赖“先看当前节点 cnt，再看左右孩子 len”的逻辑，需要你在更新完叶子后向上走的过程中不断判断当前节点的情况，写起来要格外小心。
我个人是“递归和迭代混着用”：数据范围小、时限宽裕时写递归版，代码清晰好查错；数据范围大、时限紧的时候才把 update 改成迭代。不建议初学者一上来就追 zkw，因为调试难度和心智负担会掩盖掉优化本身的效果。
4.4 真正“卡常”的核心：让访问模式更连续
上面那些都属于基本功。真正让我在一次比赛中从 TLE 翻盘到 AC 的，是一个更土的操作：把“每条边”存成 x1、x2、y、delta 四个独立数组，而不是一个结构体数组。为什么？因为 update 里访问最多的是 x1 和 x2（用于算区间边界），如果它们和 y、delta 混在一个结构体里，CPU 缓存的一次加载可能只用到其中两个成员，剩下的空间被浪费了。拆成独立数组后，连续访问 x1 数组时，缓存命中率会明显提高。
这听起来很玄学，但实测效果不小。我那次的题是求矩形周长并，矩形数量 1e5 级别，拆数组后从 2300ms 降到 1400ms，直接卡过 1500ms 的时限。后来我把同样的思路用在面积并上，虽然没有那么夸张，但也稳定快了 20% 左右。
还有一个小优化是：如果坐标都是整数，尽量用 long long 而不是 double 来存储离散化数组和线段树长度。long long 的加减和比较都比 double 快，而且能在整数上避免浮点误差。只有当坐标输入就是浮点、而且需要按原始精度输出时，才不得已保留 double。
5. 调试扫描线程序时，最容易绊倒人的五个隐蔽错误
5.1 多组数据没清空，或者“清空得不够干净”
扫描线题经常是 “多组测试数据，读到 EOF 结束”，每组数据之间你要清空线段树的 cnt 和 len。如果只清 len，不清 cnt，那第二组数据的矩形会在第一组残留的覆盖次数上继续叠加，答案直接起飞。如果 sort 和 build 的区间范围写错了，也可能只清了部分节点。我的经验是写一个清空函数把整棵线段树数组从头到尾 memset 成 0，这样虽然花一点点时间，但比逐个节点清零更让人安心。
另一个隐蔽场景是：如果你在代码里把离散化数组 xs 当成全局变量，但每组数据矩形数量不同，xs 的长度也会不同。如果有一次没把 xs 重新构建完整，lower_bound 的查找区间就不对，轻则答案错误，重则 lower_bound 返回 xs.end()，你再拿这个当下标去 update，直接越界。出现 “莫名其妙 Re 但本地跑没问题” 的情况，十有八九是这个。
5.2 扫描顺序：为什么排序关键字是 y，而不是 x
扫描线的“扫”是沿着某一维按顺序推进。求面积并时，我们通常把矩形的水平边按 y 坐标排序，从下往上扫，每次遇到一条底边（矩形下边界）就覆盖 [x1, x2)，遇到顶边（矩形上边界）就取消覆盖。如果你按 y 从大到小扫，也能算，但逻辑上所有 delta 的正负就得反过来，很容易弄混。
有一个更隐蔽的坑：当两条水平边的 y 坐标相等时，它们的上下属性会干扰计算。比如一个矩形的顶边和另一个矩形的底边在同一个 y 值上，你如果先处理底边后处理顶边，就会在同一个高度上让覆盖面积产生一个“不该出现的微小增加”，虽然理论上最后总面积不变，但在求周长、或者需要精确记录每段覆盖变化的题里，这会导致答案差异。
我的建议是：排序时除了按 y 升序外，顺手把 delta 也做一个稳定排序的逻辑，保证“先加后减”。很多模板写的是“如果 y 相同，delta 大的在前”，因为底边是加一，顶边是减一，底边在前符合面积交叠的直观直觉。不过你必须明白，这不是唯一正解，关键是让同 y 的边保持一个你确定的一致性顺序，然后仔细核对你的答案在边界情况下是否稳定。
5.3 上下边界的 delta 正负号，别只靠“感觉”写
从下往上扫，当前扫描线高度以上的区域才是还未处理的，所以底边进入扫描范围，意味着有一段 x 区间开始被覆盖，delta 是 +1；顶边经过后，那段区间退出覆盖，delta 是 -1。写成代码后，就是入边 delta = 1，出边 delta = -1。这个逻辑本身不难，但如果你把 y 升序改成 y 降序，上面的结论就相反了，稍一改错，整个面积结果是负数或者翻倍。
我见过一个特别容易迷惑到人的写法：把扫描线的方向定义成“从上往下扫”但为了配合排序省一次 reverse，结果入边出边全部写反，然后面积算出来是负数，Debug 了半天才发现问题。建议在代码里用两个明确命名的常量，比如 ADD_EDGE = 1 和 REMOVE_EDGE = -1，而不要在 update 调用里写一个裸的 1 或 -1。
5.4 浮点坐标的等号陷阱
坐标是浮点时，离散化数组的 unique 和 lower_bound 需要建立在“坐标完全相等”的假设上。如果题目输入的坐标是通过浮点运算产生的，比如 0.1 + 0.2 和 0.3，它们在二进制表示下不相等，那你 unique 根本去重不了，lower_bound 也可能查不到。结果就是区间更新时找错下标，长度算错。
遇到这种题，有几种应对方法。一是使用 long double，但 double 都搞不定的等号问题，long double 一样可能存在。二是干脆把坐标读入时四舍五入到整数，用 long long 存储，这是最稳的，前提是题目保证坐标的小数点位数有限且不会因为运算产生精度尾差。三是把输入当成字符串读进来再做转换，统一规格，不过这样做代码量会变大。反正我自己的原则是：能用整数绝不用浮点，扫描线上所有长度计算、二分查找全部建立在整数坐标上，只有最终输出面积时再转成浮点。
5.5 update 区间 [l, r] 和 [l, r-1] 的边界老搞错
这个错误几乎人人都会犯。你从 lower_bound 拿到 x1 下标 l 和 x2 下标 r 后，鲜花的段区间是 [l, r-1]。假如 x1 = 1、x2 = 3，离散化数组 {1, 3, 5}，l = 0, r = 1，你要更新的是段 0，也就是 [1,3) 这一段。如果你手滑写了 update(1, 1, m, l, r)，那就把段 1（[3,5)）也一起更新了，面积自然偏大。
调试这类问题，最好的办法是在小样例上手动跑一遍，把所有 update 区间打印出来，和离散化段列表对照。别只盯着最终答案看，面积差一点时，你根本不知道是覆盖次数错还是长度合并错。打印出每次 update 的 [l, r-1] 和对应原始坐标区间，一眼就能看出来。
6. 从我的一次真实比赛经历说起：扫描线题如何在时限边缘保命
最后说一段我自己的考试经历。当时是一道矩形周长并，n 是 2e5，时限 1200ms。我一开始用最标准的递归线段树加结构体边数组，自己本地跑极限数据刚好 1300ms，交上去果然 TLE。当时感觉很绝望，因为逻辑上觉得已经没什么可优化的了。
后来我把几个优化全部做了一遍：边数组拆成四个独立数组，给每条边的 x1、x2 预先二分好下标，把 update 函数里的 double 访问全部改成 long long，再把线段树从递归改成自底向上的迭代写法。整套改完，本地极速数据从 1300ms 掉到 750ms，交上去一把过。有同学问我哪一步起效最大，说实话很难精确归因，每一步大概都挤出了 10% 到 20% 的时间，合在一起就是质变。
就是在这样反复“被卡常”的过程中，我越来越确信：扫描线这类题目，算法层面的复杂度瓶颈通常不难，真正决定过不过的是你对细节的掌控——从离散化段定义，到线段树维护变量，再到二分的定位方式，最后落实到内存布局和读写优化。标题里那五个词，之所以总被搜索热词绑定在一起，就是因为它们在实战里根本拆不开。
