扫描线总结

引入

面积并（周长并）
如下图给你一堆矩形求它的面积并或周长并。

显然直接做，就是考虑容斥，但明显不好做。
那就思考如何切割或补，显然补完要减的图形也不规整，只能考虑割。
如何将其割成规整的图形，明显矩形最容易计算和割。
把它割成矩形后发现，每次遇到某个矩形的边就会变，所以考虑一条线从下向上扫，每遇到一个与扫描线平行的边就计算一次答案。
面积并答案为线上被覆盖的长度乘与上一条边的距离。
周长并答案分俩个部分，平行的就是线上被覆盖的长度，垂直的就是线上有多少个端点（在线段内的不算）乘与上一条边的距离。
如何快速维护线上的覆盖长度和有多少段点，显然一个区间修改问题，用线段树。

代码实现

周长并

#include <bits/stdc++.h>
using namespace std;
const int N=5e4+10;
int n,ans,cnt,mx=-100010,mi=100010,las=0;
struct node
{
    int h,x,y,w;
}bi[N*2];
bool cmp(node x,node y)
{
    if(x.h==y.h)
        return x.w>y.w;//先加后减，不让会错
/*
2
0 0 4 4
0 4 4 8
*/

    return x.h<y.h;
}
struct stu
{
    int sum;//整个区间被整体覆盖了几次（类似lazytag，但不下传)
    int num;//整个区间被几条互不相交的线段覆盖
    int len;//整个区间被覆盖的总长度
    bool lflag,rflag;
}sh[N*4];
void pushup(int x,int l,int r)
{
    if(sh[x].sum)
    {
        sh[x].num=1;
        sh[x].len=r-l+1;
        sh[x].lflag=sh[x].rflag=1;
    }
    else if(l==r)
    {
        sh[x].num=0;
        sh[x].len=0;
        sh[x].lflag=sh[x].rflag=0;
    }
    else 
    {
        sh[x].num=sh[x<<1].num+sh[x<<1|1].num;
        if(sh[x<<1].rflag&&sh[x<<1|1].lflag)sh[x].num--;
        sh[x].len=sh[x<<1].len+sh[x<<1|1].len;
        sh[x].lflag=sh[x<<1].lflag;
        sh[x].rflag=sh[x<<1|1].rflag;
    }
}
void modify(int x,int l,int r,int lt,int rt,int w)
{
    if(lt<=l&&rt>=r)
    {
        sh[x].sum+=w;
        pushup(x,l,r);
        return ;
    }
    int mid=(l+r)>>1;
    if(lt<=mid)modify(x<<1,l,mid,lt,rt,w);
    if(rt>mid)modify(x<<1|1,mid+1,r,lt,rt,w);
    pushup(x,l,r);
    return;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int x1,y1,x2,y2;scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        bi[++cnt].h=y1,bi[cnt].w=1,bi[cnt].x=x1,bi[cnt].y=x2;
        bi[++cnt].h=y2,bi[cnt].w=-1,bi[cnt].x=x1,bi[cnt].y=x2;
        mx=max(mx,x2);
        mi=min(mi,x1);
    }
    if(mi<0)
    {
        for(int i=1;i<=cnt;i++)
        {
            bi[i].x+=-mi+1;
            bi[i].y+=-mi+1;//加一与mx相匹配
        }
        mx-=mi;
    }
    sort(bi+1,bi+cnt+1,cmp);
    for(int i=1;i<=cnt;i++)
    {
        modify(1,mi,mx,bi[i].x,bi[i].y-1,bi[i].w);//减一是因为这是长度为1的叶子的右端点，叶子的编号是左端点即右端点-1.
        while(bi[i+1].h==bi[i].h&&bi[i+1].w==bi[i].w)
        {
            i++;
            modify(1,mi,mx,bi[i].x,bi[i].y-1,bi[i].w);
        }//同一类型一起处理
        ans+=abs(sh[1].len-las);//覆盖长度的变化
        las=sh[1].len;
        ans+=sh[1].num*2*(bi[i+1].h-bi[i].h);//垂直的边的长度
    }
    printf("%d",ans);
    return 0;
}

面积并

#include <bits/stdc++.h>
using namespace std;
const int N=5e5+10;
#define int long long
int n,ans,xx[N],cnt,mx=1e9+7,mi=0,las=0;
struct node
{
    int h,x,y,w;
}bi[N*2];
bool cmp(node x,node y)
{
    return x.h<y.h;
}
struct stu
{
    int sum;//整个区间被整体覆盖了几次（类似lazytag，但不下传)
    int len;//整个区间被覆盖的总长度
}sh[N*4];
void pushup(int x,int l,int r)
{
    if(sh[x].sum)sh[x].len=xx[r+1]-xx[l];
    else if(l==r)sh[x].len=0;
    else sh[x].len=sh[x<<1].len+sh[x<<1|1].len;//除了覆盖长度外都不要了
}
void modify(int x,int l,int r,int lt,int rt,int w)
{
    if(lt<=l&&rt>=r)
    {
        sh[x].sum+=w;
        pushup(x,l,r);
        return ;
    }
    int mid=(l+r)>>1;
    if(lt<=mid)modify(x<<1,l,mid,lt,rt,w);
    if(rt>mid)modify(x<<1|1,mid+1,r,lt,rt,w);
    pushup(x,l,r);
    return;
}
signed main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
    {
        int x1,y1,x2,y2;scanf("%lld%lld%lld%lld",&x1,&y1,&x2,&y2);
        if(x1>x2)swap(x1,x2);
        if(y1>y2)swap(y1,y2);
        bi[++cnt].h=y1,bi[cnt].w=1,bi[cnt].x=x1,bi[cnt].y=x2;
        bi[++cnt].h=y2,bi[cnt].w=-1,bi[cnt].x=x1,bi[cnt].y=x2;
        mx=max(mx,bi[cnt].y);
        mi=min(mi,bi[cnt].x);
        xx[i]=bi[cnt].x;
		xx[i+n]=bi[cnt].y;
    }
    sort(xx+1,xx+2*n+1);
    int tot=unique(xx+1,xx+2*n+1)-xx-2;
    sort(bi+1,bi+cnt+1,cmp);
    for(int i=1;i<=cnt;i++)
    {
        int x=lower_bound(xx+1,xx+tot+2,bi[i].x)-xx;
        int y=lower_bound(xx+1,xx+tot+2,bi[i].y)-xx-1;//离散化了
        modify(1,1,tot,x,y,bi[i].w);
        ans+=sh[1].len*(bi[i+1].h-bi[i].h);
    }
    printf("%lld",ans);
    return 0;
}