扫描线
2025-12-27
Intro
一般运用在图形上,例如求矩形的面积并。
具体来看就跟它的名字一样,一条线在坐标轴上扫。
二维矩形面积并问题
在一个平面直角坐标系内,给定矩形左下和右上两个点,求多个矩形的面积并。
像这幅图一样,按 x 排序后实际只需要直到被分割出来的条的长度,可以使用线段树维护(可能需要离散化)。
每次讲矩形左边 +1,右边 −1,最后查询 1∼n 所有值 >0 的位置即可。
具体的,需要维护 cnt 表示当前区间被覆盖的次数,len 表示当前区间被覆盖的长度。
容易发现,cnt>0 时当前区间被覆盖的长度就是当前区间的长度。
若 cnt=0 则区间被覆盖长度为左右儿子的 len 的和。
但这并不好维护,并且效率很低,因为每次都要查询根节点,考虑优化。
- 由于每个操作都成对出现,所以在
modify中的pushdown并没有作用。
对于 −1 操作且 cnt=1,我们事实上需要用左右两个节点的 len,但这个时候尽管不维护pushdown它们的值也是正确的。 - 由于只需要保证根节点信息正确,所以压根不会运行到分裂时使用的
pushdown。
综上,我们可以直接丢掉 pushdown,然后就可以直接做了。
