hdu1828 扫描线计算周长

和扫描线计算面积差不多，新加了lbd，rbd线段树来标记区间的左右两侧是否被填充(左右边界是否存在)，numbd线段树统计区间有多少边

/*数据弱不用离散化,但是要处理一下坐标*/

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

using namespace std;

#define maxn 20005

#define lson l,m,rt<<1

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

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<<];//该区间竖边的数量(0,2)

int cnt[maxn<<];//覆盖了这一整个区间的入边-出边

int 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]-=;

    }

}

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);

}

int main(){

    int n;

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

        int m=;

        int lbd=,rbd=-;

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

            int a,b,c,d;

            scanf("%d%d%d%d",&a,&b,&c,&d);

            lbd=min(lbd,a);

            rbd=max(rbd,c);

            ss[m++]=Seg(a,c,b,);

            ss[m++]=Seg(a,c,d,-);

        }

        sort(ss,ss+m);

        int ret=,last=;

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

            if(ss[i].l<ss[i].r)

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

            ret+=numseg[]*(ss[i+].h-ss[i].h);//竖边数量*区间高度

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

            last=len[];

        }

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

    }

    return ;

}