扫描线一般运用在图形上面，它和它的字面意思非常相似，就是拿一根线，在图形上面扫来扫去。我们一般用它来解决图形的面积，周长，二位数点等问题。

在二维坐标系上，给出多个矩形的左下以及右上坐标，求出所有矩形构成的图形的面积。

我们当然知道，如果数据范围很小，我们可以直接暴力，也就是先都加起来，然后再枚举一下把重复的减去；但如果数据范围过大，我们暴力肯定是不行的，这个时候就可以用到我们的扫描线了。

(资料图片仅供参考)

假设我们现在有一根线，从下往上开始扫描：

（这是张动图可能导成pdf就挂了）

我们发现，我们把整个图形分成了如图各个颜色不同的小矩形，那么这个小矩阵的高就是我们扫过的距离，那么剩下了一个变量，那就是长在不断地变化。

我们一般用线段树来维护矩形的长，我们给每一个矩形的上下边进行标记，下面的边标记为 \(1\)，上面的边标记为 \(-1\)，每遇到一个矩形的时候，我们就知道了标记为 \(1\) 的边，我们就加进来这一条矩形的长，等到扫描到 \(-1\) 的时候，证明这一条边需要删除，就删去，利用 \(1\) 和 \(-1\) 可以轻松的到达这种状态。

我们一般还需要用到离散化。

我们结合例题来看一下：

P5490【模板】扫描线 - 洛谷

我们前面说要用线段树来做，我们用它来维护当前的矩形的长。

我们考虑到我们的线段树维护的东西都是点，但是我们需要维护的是区间，那么我们可以把区间下放到点上，也就是每一个叶子节点维护的是一个线段，而我们用 \(l\)，也就是当前点的左端点，以及 $r+1 $ 来达到询问当前节点区间的左右端点的目的。

我们先来看主函数：

signed main(){    n=read();    for(int i=1;i<=n;i++)    {        x11=read(),y11=read(),x22=read(),y22=read();        X[2*i-1]=x11,X[2*i]=x22;        e[2*i-1]=(sb){x11,x22,y11,1};        e[2*i]=(sb){x11,x22,y22,-1};    }    n*=2;    sort(e+1,e+n+1,cmp);    sort(X+1,X+n+1);    int tot=unique(X+1,X+n+1)-X-1;//    cout<<"tot:"<

\(X\) 数组是用来存放所有点的横坐标，因为我们是要维护区间的话，不可能每一个点都维护到，所以只存放有给定点的坐标，\(e\) 是定义的结构体用于存放每一个矩形的信息，我们需要把他给存放下当前矩形的信息，其中 \(X[2i-1]\) 是当前矩形的左端点横坐标，\(X[2i]\) 是当前矩形的右端点横坐标，\(e[2i-1]\) 是当前矩形的下表面，\(e[2i]\) 是当前矩形的上表面，因为我们说了如果要是碰到了下表面，我们就需要给他加进去，一旦碰到上表面，说明这个矩形完成了，可以出去了。两个 sort第一个是给矩形的上下表面按高度排序，保证是从下往上遍历的，不会出现负数，后面的是进行排序后用 unique进行离散化，然后就开始建树。因为我们是把线段放到左端点上，所以是 \(tot-1\) 个。再往后，我们进行 change操作来对当前扫到的矩形长的长度做修改，然后用上一个的高度减去当前点的高度，计算当前扫到的面积。

再来看 change操作：

inline void p_p(int x){    int l=e1[x].l,r=e1[x].r;    if(e1[x].sum)e1[x].len=X[r+1]-X[l];    else e1[x].len=e1[ls].len+e1[rs].len; }inline void change(int x,int nl,int nr,int c){    int l=e1[x].l,r=e1[x].r;    if(X[r+1]<=nl||nr<=X[l])return ;    if(nl<=X[l]&&X[r+1]<=nr)    {        e1[x].sum+=c;        p_p(x);        return ;    }    change(ls,nl,nr,c);    change(rs,nl,nr,c);    p_p(x);    return ;}

我们的 change里面是用来修改当前扫到的矩形的长的长度总和的。

如果要是当前的区间右端点在要改的左端点的左边，那肯定不会包含，直接退出；如果当前区间左端点在要改的右端点的右边，那肯定也不包含，直接退出。

后面如果遇到包含的区间就直接改 \(sum\)，然后更新。

这个更新函数也就是 p_p是对于所有的扫到的线段长度进行求和返回到上面，如果没有扫到就直接更新儿子节点，为什么呢？因为一开始的儿子节点长度都是 \(0\)，叶子节点没有儿子节点，默认也是 \(0\)。

至此我们完成了这个奇妙的算法！

signed main(){    cin>>n;    for(int i=1;i<=n;i++)    {        cin>>x11>>y11>>x22>>y22;        X[2*i-1]=x11,X[2*i]=x22;        e[2*i-1]={x11,x22,y11,1};        e[2*i]={x11,x22,y22,-1};    }    n*=2;    sort(e+1,e+n+1,cmp);    sort(X+1,X+n+1);    int tot=unique(X+1,X+n+1)-X-1;    build(1,1,tot-1);    int res=0;    for(int i=1;i

inline void p_p(int x){    int l=t[x].l,r=t[x].r;    if(t[x].sum)    {        t[x].len=X[r+1]-X[l];        t[x].lc=t[x].rc=1;        t[x].c=1;    }    else     {        t[x].len=t[ls].len+t[rs].len;        t[x].lc=t[ls].lc,t[x].rc=t[rs].rc;        t[x].c=t[ls].c+t[rs].c;        if(t[rs].lc&&t[ls].rc)t[x].c--;    }}inline void change(int x,int nl,int nr,int c){    int l=t[x].l,r=t[x].r;    if(X[l]>=nr||nl>=X[r+1])return ;    if(nl<=X[l]&&nr>=X[r+1])    {        t[x].sum+=c;        p_p(x);        return ;    }    change(ls,nl,nr,c);    change(rs,nl,nr,c);    p_p(x);    return ; }