>做这道题我花了相当多的时间，一是由于自己的代码太长没有进行**模块化的编程**（例如求解水平和竖直周长的时候可以用相同的函数处理），二是我对**扫描线算法求解的问题特性**不够熟悉。

***

## 题目分析   
这道题很容易看出来是**扫描线算法**，因此建立扫描线和离散化处理就是非常自然的操作。但是之后有两点卡住了我：

（1）扫描线算法处理的问题一般都有一个特性，那就是**正1扫描线和负1扫描线都是一一对应**的。因此对于线段树的每一个节点，我们都可以直接用**c数组**表示该节点代表区间被扫描线覆盖的次数。若c大于0，则直接得到区间全部被覆盖；若c=0,则区间覆盖值就是子区间覆盖长度之和。

（2）周长变化应该如何维护？我之前想要对每个单位长度的覆盖次数进行维护，但这样时间复杂度极高。其实只需要每次更新扫描线后将**abs(新覆盖长度-旧覆盖长度)加入到ans**里就行。需要注意的是，这道题默认重叠边的长度算入周长，是非常坑的一个点。如果不计入重叠边的话，应该需要在先对扫描线进行预处理。

## 代码  
#include<cstdio>
#include<iostream>
#include<algorithm>

using namespace std;

const int N=5001;

struct line
{
    int st,en;
    int pos;
    int val;
    bool operator <(const line &others)const
    {
        return pos<others.pos;
    }
}v[N*2],h[N*2];

struct tree
{
    int l,r;
    int val;
    int sum,c;
}t[N*8];

int n;
int ver[N*2],hor[N*2];
int hm,vm;
int ans=0,init;

void build(int p,int l,int r)
{
    t[p].l=l;
    t[p].r=r;
    t[p].val=0;
    t[p].sum=0;
    t[p].c=0;
    if(l==r)
    {
        return;
    }
    int mid=(l+r)>>1;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    return;
}

void changeh(int p,int l,int r,int k)
{
    if(t[p].l==t[p].r)
    {
        t[p].c+=k;
        if(t[p].c)
        {
            t[p].sum=hor[t[p].r+1]-hor[t[p].l];
        }
        else
        {
            t[p].sum=0;
        }
        return;
    }
    if(t[p].l>=l && t[p].r<=r)
    {
        t[p].c+=k;
        if(t[p].c)
        {
            t[p].sum=hor[t[p].r+1]-hor[t[p].l];
        }
        else
        {
            t[p].sum=t[p*2].sum+t[p*2+1].sum;
        }
        return;
    }
    int mid=(t[p].l+t[p].r)>>1;
    if(mid>=l)
    {
        changeh(p*2,l,r,k);
    }
    if(mid+1<=r)
    {
        changeh(p*2+1,l,r,k);
    }
    if(!t[p].c)
    {
        t[p].sum=t[p*2].sum+t[p*2+1].sum;
    }
    return;
}

void changev(int p,int l,int r,int k)
{
    if(t[p].l==t[p].r)
    {
        t[p].c+=k;
        if(t[p].c)
        {
            t[p].sum=ver[t[p].r+1]-ver[t[p].l];
        }
        else
        {
            t[p].sum=0;
        }
        return;
    }
    if(t[p].l>=l && t[p].r<=r)
    {
        t[p].c+=k;
        if(t[p].c)
        {
            t[p].sum=ver[t[p].r+1]-ver[t[p].l];
        }
        else
        {
            t[p].sum=t[p*2].sum+t[p*2+1].sum;
        }
        return;
    }
    int mid=(t[p].l+t[p].r)>>1;
    if(mid>=l)
    {
        changev(p*2,l,r,k);
    }
    if(mid+1<=r)
    {
        changev(p*2+1,l,r,k);
    }
    if(!t[p].c)
    {
        t[p].sum=t[p*2].sum+t[p*2+1].sum;
    }
    return;
}

void pro()
{
    sort(ver+1,ver+n*2+1);
    vm=unique(ver+1,ver+n*2+1)-ver-1;
    sort(hor+1,hor+n*2+1);
    hm=unique(hor+1,hor+n*2+1)-hor-1;
    return;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int a,b,c,d;
        scanf("%d%d%d%d",&a,&b,&c,&d);
        ver[i*2-1]=a;
        ver[i*2]=c;
        hor[i*2-1]=b;
        hor[i*2]=d;

        v[i*2-1].st=b;
        v[i*2-1].en=d;
        v[i*2-1].pos=a;
        v[i*2-1].val=1;

        v[i*2].st=b;
        v[i*2].en=d;
        v[i*2].pos=c;
        v[i*2].val=-1;

        h[i*2-1].st=a;
        h[i*2-1].en=c;
        h[i*2-1].pos=b;
        h[i*2-1].val=1;

        h[i*2].st=a;
        h[i*2].en=c;
        h[i*2].pos=d;
        h[i*2].val=-1;
    }
    pro();
    for(int i=1;i<=n;i++)
    {
        int a=h[i*2-1].st;
        int b=v[i*2-1].st;
        int c=h[i*2-1].en;
        int d=v[i*2-1].en;

        v[i*2-1].st=lower_bound(hor+1,hor+hm+1,b)-hor;
        v[i*2-1].en=lower_bound(hor+1,hor+hm+1,d)-hor;
        v[i*2-1].pos=lower_bound(ver+1,ver+vm+1,a)-ver;
        v[i*2-1].val=1;

        v[i*2].st=v[i*2-1].st;
        v[i*2].en=v[i*2-1].en;
        v[i*2].pos=lower_bound(ver+1,ver+vm+1,c)-ver;
        v[i*2].val=-1;

        h[i*2-1].st=lower_bound(ver+1,ver+vm+1,a)-ver;
        h[i*2-1].en=lower_bound(ver+1,ver+vm+1,c)-ver;
        h[i*2-1].pos=lower_bound(hor+1,hor+hm+1,b)-hor;
        h[i*2-1].val=1;

        h[i*2].st=h[i*2-1].st;
        h[i*2].en=h[i*2-1].en;
        h[i*2].pos=lower_bound(hor+1,hor+hm+1,d)-hor;
        h[i*2].val=-1;
    }
    sort(v+1,v+n*2+1);
    sort(h+1,h+n*2+1);

    //竖直方向的周长
    build(1,1,hm-1);
    init=0;
    for(int i=1;i<=n*2;i++)
    {
        int st=v[i].st;
        int en=v[i].en-1;
        int op=v[i].val;
        changeh(1,st,en,op);
        ans+=abs(init-t[1].sum);
        init=t[1].sum;
    }

    //水平方向的周长
    build(1,1,vm-1);
    init=0;
    for(int i=1;i<=n*2;i++)
    {
        int st=h[i].st;
        int en=h[i].en-1;
        int op=h[i].val;
        changev(1,st,en,op);
        ans+=abs(init-t[1].sum);
        init=t[1].sum;
    }

    printf("%d",ans);
    return 0;
}