poj1177 矩形周长并

线段树扫描线的模板题，一个月前写的发现忘了一些还是要看看以前的博客呀！

/*

思路：数据小不用离散化处理，线段树叶子结点维护一个区间

*/

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

using namespace std;

#define maxn 20005

struct Seg{

    int l,r,h,s;

    Seg(){}

    Seg(int a,int b,int c,int d):l(a),r(b),h(c),s(d){}

    bool operator<(const Seg & a)const {

        //if(h==a.h) return s>a.s;

        return h<a.h;

    }

}ss[maxn];

bool lbd[maxn<<],rbd[maxn<<];//被覆盖的区域是否和左右区间线重合

int numseg[maxn<<],cnt[maxn<<],len[maxn<<];

void pushup(int rt,int l,int r){

    if(cnt[rt]){

        lbd[rt]=rbd[rt]=;

        len[rt]=r-l;

        numseg[rt]=;

    }

    else if(l+==r)

        len[rt]=numseg[rt]=rbd[rt]=lbd[rt]=;

    else {

        lbd[rt]=lbd[rt<<];

        rbd[rt]=rbd[rt<<|];

        len[rt]=len[rt<<]+len[rt<<|];

        numseg[rt]=numseg[rt<<]+numseg[rt<<|];

        if(lbd[rt<<|] && rbd[rt<<]) numseg[rt]-=;

    }

}

#define lson l,m,rt<<1

#define rson m,r,rt<<1|1

void update(int L,int R,int c,int l,int r,int rt){

    if(L<=l && R>=r){

        cnt[rt]+=c;

        pushup(rt,l,r);

        return;

    }

    int m=l+r>>;

    if(L<m) update(L,R,c,lson);

    if(R>m) update(L,R,c,rson);

    pushup(rt,l,r);

}

void init(){

    memset(lbd,,sizeof lbd);

    memset(rbd,,sizeof rbd);

    memset(cnt,,sizeof cnt);

    memset(len,,sizeof len);

    memset(numseg,,sizeof numseg);

}

int main(){

    int n;

    while(scanf("%d",&n)==){

        init();

        int m=,x1,y1,x2,y2,lbd=,rbd=-,last=,ans=;

        for(int i=;i<=n;i++){

            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);

            ss[m++]=Seg(x1,x2,y1,);

            ss[m++]=Seg(x1,x2,y2,-);

            lbd=min(lbd,x1),rbd=max(rbd,x2);

        }

        sort(ss,ss+m);

        for(int i=;i<m;i++){

            update(ss[i].l,ss[i].r,ss[i].s,lbd,rbd,);

            ans+=abs(len[]-last);last=len[];

            ans+=numseg[]*(ss[i+].h-ss[i].h);

        }

        printf("%d\n",ans);

    }

    return ;

}