P1856 [USACO5.5]矩形周长Picture 题解

Link

P1856 [USACO5.5]矩形周长Picture

Solve

这道题也是非常经典的扫描线问题，我们把图形分成几块，每次就需要累加这一次的答案和上一次的答案的差就好了

然后横着刷一遍，竖着刷一遍就好了

有些细节要注意，就是要在同一层的线，要先加边后删边

Code

    #include <iostream>
    #include <algorithm>
    #include <stdio.h>
    #include <math.h>
    using namespace std;
    typedef long long LL;
    int tree[80020],lazy[80020],cnt[80020];
    #define ls nod<<1
    #define rs nod<<1|1
    void pushdown(int nod,int l,int r){
        if(lazy[nod]){
            lazy[ls]+=lazy[nod];cnt[ls]+=lazy[nod];
            lazy[rs]+=lazy[nod];cnt[rs]+=lazy[nod];
            lazy[nod]=0;
        }
    }
    void pushup(int nod,int l,int r){
        if(cnt[ls]==cnt[rs]){cnt[nod]=cnt[ls];tree[nod]=tree[ls]+tree[rs];}
        else if(cnt[ls]<cnt[rs]){cnt[nod]=cnt[ls];tree[nod]=tree[ls];}
        else{cnt[nod]=cnt[rs];tree[nod]=tree[rs];}
    }
    void build(int nod,int l,int r){
        lazy[nod]=0;
        if(l==r){cnt[nod]=lazy[nod]=0;tree[nod]=1;return;}
        int mid=l+r>>1;
        build(ls,l,mid);build(rs,mid+1,r);
        pushup(nod,l,r);
    }
    void ins(int nod,int l,int r,int x,int y,int v){
        if(l==x&&r==y){
            lazy[nod]+=v;
            cnt[nod]+=v;
            return;
        }
        pushdown(nod,l,r);
        int mid=l+r>>1;
        if(y<=mid)ins(ls,l,mid,x,y,v);
        else if(x>mid)ins(rs,mid+1,r,x,y,v);
        else{ins(ls,l,mid,x,mid,v);ins(rs,mid+1,r,mid+1,y,v);}
        pushup(nod,l,r);
    }
    int n;LL x,ans;
    struct bar{int a,b,c,d;bar(){}bar(int w,int x,int y,int z){a=w;b=x;c=y;d=z;}}b[5003],c[20003];
    bool operator<(bar a,bar b){return a.a!=b.a?a.a<b.a:a.d>b.d;}
    void doit(){
        sort(c+1,c+2*n+1);build(1,1,20002);
        for(int i=1;i<=n+n;i++){
            x=tree[1]*(cnt[1]==0);
            ins(1,1,20002,c[i].b,c[i].c,c[i].d);
            ans+=abs(x-tree[1]*(cnt[1]==0));
        }
    }
    int main(){
    	freopen("P5490.in","r",stdin);
    	freopen("P5490.out","w",stdout);
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d%d%d%d",&b[i].a,&b[i].b,&b[i].c,&b[i].d);
            b[i].a+=10001;b[i].b+=10001;b[i].c+=10001;b[i].d+=10001;
            c[2*i-1]=bar(b[i].b,b[i].a,b[i].c-1,1);
            c[2*i]=bar(b[i].d,b[i].a,b[i].c-1,-1);
        }
        doit();
        for(int i=1;i<=n;i++){
            c[2*i-1]=bar(b[i].a,b[i].b,b[i].d-1,1);
            c[2*i]=bar(b[i].c,b[i].b,b[i].d-1,-1);
        }
        doit();
        printf("%lld",ans);
        return 0;
}