扫描线

· · 个人记录

一般用于解决二维区间问题

思想非常简单，就是类似一根线在从左到右（从下到上）扫，对于每个“节点”维护“整体”信息，不关注内部情况。

定义节点：扫描线“停下”的位置（产生修改/查询的位置）

考虑整体和极端。——C.

基本问题：矩形面积并

OI-wiki 好图/bx

我们发现扫描线扫过的面积是由一些横向矩形拼起来的，上下为相邻的“横线”时长不变（即为当前被“覆盖”的长度）

数据结构维护横向，扫描线扫纵向，计算每个矩形的大小。

具体怎么做呢？

看一道模板题

key1：扫描线往往配合离散化

扫描线的复杂度只与节点的数量有关，与值域无关

比如此题，值域 1e9 但实际上只有 2e5 个节点

下文引用一篇博客

考虑如何维护区间被覆盖的长度

显然对于矩形下边，执行区间加；对于上边，执行区间减

自然需要维护区间的“覆盖次数”

但并不是被覆盖到的次数，而是被完全覆盖的次数

why？因为“覆盖到”并不清楚到底是覆盖了哪些子区间，在对整个区间做减法的时候，需要对儿子一个一个修改（每个都要 -1）

key2：线段树不带 lazytag

发现矩形并的区间修改具有很好的性质：

  1. 区间加和区间减一一对应，且都是在同一个区间上操作
  2. 区间减一定在对应的区间加后，即做减法时区间一定已经被覆盖过

所以可以直接在对应的节点上修改，不需要有 lazytag

why？

假设 [5,8] 被覆盖 1 次，[7,8] 被覆盖 1 次

现在对 [7,8] 执行区间减，会影响到 [5,8] 吗？不会

[5,8] 被覆盖 1 次 2 次或 10 次对 [7,8] 区间 -1 有影响吗？没有

所以可以无视 [5,8] 直接修改

实际上，不需要 lazytag 是因为，不管怎么修改儿子，都不会影响到被完全覆盖过的父亲。只有覆盖和没覆盖的区别，没有覆盖多少次的区别。

key3：上传信息

if(cnt[x]) len[x]=z[r+1]-z[l];//完全覆盖，覆盖长度就是区间长度
else len[x]=len[ls[x]]+len[rs[x]];//否则用左儿子 + 右儿子

一定不能 pushup 只有下面一行，在 upd 完全覆盖区间才执行上面一行（由于 ls 和 rs 不一定被访问过，len 的和可能小于 x 的 len，会覆盖掉上面的修改）

这导致我调了 0.5+h/kk

完整代码

（待修）