扫描线

扫描线是一种用来处理矩形相交的面积问题的算法
渐近时间复杂度约为O(nlogn)O(nlogn)
Q1.
在坐标系给定n个矩形(以左下/右上角坐标给出)
求这些矩形面积的并

例如下图
n=2
矩形1: (1,1) (3,3)
矩形2: (2,2) (4,4)

A1.
扫描线的过程大致可以描述为
将整个面积并以n个矩形的 2n条纵边为界分割为2n-1个部分求解

即上图中我们作如下分割求解

我们要求的面积就是ans=S1+S2+S3ans=S1+S2+S3
再细致一点讲
我们记录每条纵边并按x坐标升序排序
依次遍历每条纵边边，同时记录当前纵边覆盖的y轴总长度len
遍历到的纵边为一个矩形的左边界时，len增加
反之为右边界时，len减小
根据当前遍历到的纵边ii更新完len后
令ans+=(xi+1−xi)∗lenans+=(xi+1−xi)∗len （xi+1xi+1为下一条扫描线的横坐标,xixi为当前扫描线横坐标）

最关键的问题来了，len是如何更新的呢
设一个矩形表示为(x1,y1)(x2,y2)(x1,y1)(x2,y2)
我们记录这个矩形的扫描线为两个四元组
(x1,y1,y2,k=1)(x2,y1,y2,k=−1)(x1,y1,y2,k=1)(x2,y1,y2,k=−1)其中左边界记录的扫描线k=1，右边界则为-1
最后我们共记录了2n条扫描线

定义cov[i]=vcov[i]=v表示yy轴上ii共被覆盖了vv次
将这些扫描线按x升序排序后
设当前遍历到的扫描线为(xi,yi,1,yi,2,k)(xi,yi,1,yi,2,k)
我们令cov[yi,1]cov[yi,1]~cov[yi,2]cov[yi,2]都加k，即更新此时的覆盖情况
那么此时有len=−1+∑cov[i]>01len=−1+∑cov[i]>01
更新ans+=(xi+1−xi)∗lenans+=(xi+1−xi)∗len
对cov数组的更新显然可以用线段树优化
且注意到这里扫描线的修改区间都是成对出现的(即一次+1一次-1)
我们不采用延迟标记的方式
而是直接修改每个区间对应的logn个结点

len[p]表示结点p表示的区间内被覆盖的总长度
对某个结点修改cov时和从下向上传递标记时
进行如下更新

void pushup(int p,int ll,int rr)
{
    if(cov[p]>0) len[p]=rr-ll;
    else if(ll==rr) len[p]=0;
    else len[p]=len[p<<1]+len[p<<1|1];
}

修改完后当前的总覆盖区间就是len[rt]

注意扫描线的题一般y都很大，且存在浮点数
所以要对y进行离散化
(val[yi]val[yi]表示yiyi离散化后的数值，pos[i]pos[i]表示ii对应的原数值)
离散化后对于四元组(xi,yi,1,yi,2,k)(xi,yi,1,yi,2,k)
我们的更新区间为[val[yi,1],val[yi,2]−1][val[yi,1],val[yi,2]−1]
而对应的上推变为

扫描线

全站热榜