【详解】线段树扫描线

题目

「VOJ1056」图形面积

桌面上放了$N$N个平行于坐标轴的矩形，这$N$N个矩形可能有互相覆盖的部分，求它们组成的图形的面积。
【输入】
有多组测试数据。
每组测试数据输入第一行为一个数$N$N，表示矩形的数量。
下面$N$N行，每行四个整数，分别表示每个矩形的左下角和右上角的坐标，坐标范围为$–10^8$–108到$10^8$108之间的整数。
当$N==0$N==0时，测试文件结束。
【输出】
对于每个测试用例，在单独一行中输出一个整数，表示图形的面积。
【样例输入】

1
1 2 3 4
3
1 1 4 3
2 -1 3 2
4 0 5 2
0

【样例输出】

4
10

【数据范围】
对于$50\%$50%的数据，$0<N<=100$0<N<=100，每个测试点测试数据组数$<=20$<=20。
对于$50\%$50%的数据，坐标范围为$–500$–500到$500$500之间的整数。
对于$100\%$100%的数据，$0<N<=2000$0<N<=2000，每个测试点测试数据组数$<=50$<=50，坐标范围为$–10^8$–108到$10^8$108之间的整数。

线段树扫描线

线段树扫描线就是用来解决图像面积并的问题。
例如存在下面三个矩形：

我们可以根据矩形的左右边界分成多个部分求解：


这些红色的线就称为扫描线。

扫描线

从左往右扫过矩形左右边，每两条扫描线之间的面积总和就是图形面积。
每一段面积 = （覆盖扫描线上的长度和）*（与下一条扫描线的距离）。
可以发现，影响扫描线上的覆盖长度，只与矩形左右边相关，因此可以将图形简化：

构造一个四元组$line(x,y,yy,flag)$line(x,y,yy,flag)，即结构体，来存在这些矩形左右边。
$x$x：边的横坐标；
$y,yy$y,yy：边的两个端点，长度为yy-y；
$flag$flag：$1$1表示矩形的左边界，$-1$−1表示矩形的右边界。

在扫描线上的覆盖长度，可以看作边在$y$y轴上的投影，我们将投影分成多段区间：

每一条边的投影包含连续的多段区间，求扫描线的覆盖总长度，其实就是多段区间的覆盖长度。
如果将每段区间看作序列中的一个点，就相当于线段树的区间修改、区间求和。
（1）构造一个线段树维护的序列，每个点对应一个区间。
因为纵坐标$y$y有重复，需要去重排序。设去重排序后的序列为$dy[]$dy[]，有$t$t个。分成$t-1$t−1段区间。
那么第$i$i段区间的左端点为$dy[i]$dy[i],区间长度为$dy[i+1]-dy[i]$dy[i+1]−dy[i]。

再添加两个数组：
$cnt[k]$cnt[k]：表示线段树结点$k$k表示区间的覆盖次数。
$len[k]$len[k]：表示线段树结点$k$k表示覆盖区间的长度。
（2）对于每一条边$line(x,y,yy,flag)$line(x,y,yy,flag)，相当于对覆盖的区间结点进行增加$flag$flag。
如何找到$y$y和$yy$yy对应哪一段区间？
二分查找，因为$dy[]$dy[]已经是去重且有序的。
需要注意边界情况：
$yy=Half()-1$yy=Half()−1，$yy>y$yy>y，表示第$Half()-1$Half()−1段区间，区间为$[ dy[ef()-1] , dy[ef()] )$[dy[ef()−1],dy[ef()])。$Half()$Half()为二分函数。
同时根据$cnt[k]$cnt[k]覆盖次数更新结点：
当覆盖次数为$0$0时，结点代表的区间不参与计算。

	if(cnt[k]!=0) len[k]=dy[r+1]-dy[l];			//进行了覆盖，区间长度就是第l段~第r段区间的长度
	else len[k]=len[2*k]+len[2*k+1];			//没有覆盖，区间长度就是左右孩子区间长度之和

（3）区间求和，求投影到$y$y轴的覆盖区间。
对于两条边$line_1(x_1,y_1,yy_1,flag_1)，line_2(x_2,y_2,yy_2,flag_2)$line1​(x1​,y1​,yy1​,flag1​)，line2​(x2​,y2​,yy2​,flag2​)
扫描线之间的宽度就是$x_2-x_1$x2​−x1​
扫描线上的覆盖长度是$len[1]$len[1]
两条扫描线之间的面积：
$len*(x2-x1)$len∗(x2−x1)
$ans+=len*(x2-x1)$ans+=len∗(x2−x1)，$ans$ans就是最后的答案。

参考程序

#include<bits/stdc++.h>
#define N 2010
#define LL long long
using namespace std;
struct Line
{
    int x,y,yy,flag;    //扫面线，横坐标为x，长度为y~yy 
}line[2*N];
struct Tree
{
    LL len;
    int cnt;
}tree[10*N];//cnt统计区间覆盖次数,len统计覆盖的区间长度
int n;
int temp[2*N],dy[2*N],t;     
void dist()             //纵坐标去重排序
{
    sort(temp+1,temp+n+1);
    dy[++t]=temp[1]; 
    for(int i=2;i<=n;i++)
        if(temp[i]!=temp[i-1]) dy[++t]=temp[i];
    t--;        //有t个点，分成t-1个段区间 
    return;
} 
int comp(Line a,Line b)
{
    return a.x<b.x?1:0;
}
void built(int k,int l,int r)   //建树，初始化，第k个结点表示区间[dy[l],dy[l+1]] 
{
    tree[k].len=0;               
    tree[k].cnt=0;
    if(l==r)    return;
    int mid=(l+r)/2;
    built(2*k,l,mid);
    built(2*k+1,mid+1,r);
}
int Half(int k)         //二分查找纵坐标对应那一段区间 
{
    int l=1,r=t+1;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(dy[mid]==k) return mid;
        if(dy[mid]<k) l=mid+1;
        else r=mid-1; 
    }
}
void pushdown(int k,int l,int r)
{
    if(tree[k].cnt>0) tree[k].len=dy[r+1]-dy[l]; //覆盖的区间长度 
    else tree[k].len=tree[2*k].len+tree[2*k+1].len;
}
void update(int k,int l,int r,int X,int Y,int T)
{
    if(l>Y||r<X) return;  //第l~r段区间，是[dy[l],dy[r+1])
    if(X<=l&&r<=Y)
    {
        tree[k].cnt+=T;
        pushdown(k,l,r);
        return;
    }
    int mid=(l+r)/2;
    update(2*k,l,mid,X,Y,T);
    update(2*k+1,mid+1,r,X,Y,T);
    pushdown(k,l,r);                //回溯更新len 
}
int main()
{
    while((scanf("%d",&n))&&n)
    {
        LL ans=0;
        t=0;
        int a,b,c,d;
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d%d%d",&a,&b,&c,&d);
            line[2*i-1]=Line{a,b,d,1};      //矩形左边界 
            line[2*i]=Line{c,b,d,-1};       //矩形右边界 
            temp[2*i-1]=b;          //纵坐标 
            temp[2*i]=d;
        }
        n*=2;
        dist(); //纵坐标去重排序  
        built(1,1,t);
        sort(line+1,line+n+1,comp);     //扫描线排序
        for(int i=1;i<=n;i++)
        {
            if(i>1&&line[i].x!=line[i-1].x)  ans+=(line[i].x-line[i-1].x)*tree[1].len;
            int X=Half(line[i].y),Y=Half(line[i].yy)-1;      
            update(1,1,t,X,Y,line[i].flag);
        }
        printf("%lld\n",ans);
    } 
    return 0;
 }