扫描线+离散化+线段树+二分+卡常：矩形面积并实战

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 是否被覆盖那你会遇到一个经典问题两个矩形在 x3 这条边界上的覆盖次数会不会被算重答案会。因为矩形 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 对应下标 lx2 对应下标 r然后让线段树去更新区间 [l, r-1]。vectordouble 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、右儿子 2u1于是顺手把离散化后的下标也改成从 1 开始。这没问题但要记住线段树里维护的是“段”不是“点”。假设离散化后有 m 个坐标点那线段树的叶子应该对应 m-1 个段索引从 0 到 m-2对应段 [xs[0], xs[1])、[xs[1], xs[2])……如果你强行让叶子从 1 开始就得写 idx1很容易绕晕。我个人的习惯是离散化数组下标从 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[r1] - 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] 大于 0len[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[r1]如果 r 已经是 m-2 的段编号r1 就是 m-1下标不越界但如果你错误地把段数当成 m或者在 build 时把区间端点写成 0 到 m访问 xs[r1] 就会越过数组末尾。空间开大一点至少能把这种越界变成“稀奇古怪的答案”而不是“直接段错误”更容易定位。第二个原因是部分题目不止一维扫描线可能在二维线段树或者动态开点和静态数组之间切换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% 的时间合在一起就是质变。就是在这样反复“被卡常”的过程中我越来越确信扫描线这类题目算法层面的复杂度瓶颈通常不难真正决定过不过的是你对细节的掌控——从离散化段定义到线段树维护变量再到二分的定位方式最后落实到内存布局和读写优化。标题里那五个词之所以总被搜索热词绑定在一起就是因为它们在实战里根本拆不开。