hdu 1828 Picture（线段树扫描线矩形周长并）

线段树扫描线矩形周长并

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cmath>

#define MAXN 22222

using namespace std;

int len[MAXN<<2];

bool lbd[MAXN<<2],rbd[MAXN<<2];

int numseg[MAXN<<2];

int cnt[MAXN<<2];

struct line

{

    int s,e,h,type;

}L[MAXN];

bool cmp(line a,line b)

{

    if(a.h==b.h)return a.type>b.type;

    return a.h<b.h;

}

void pushup(int num,int l,int r)

{

    if(cnt[num])//全部覆盖

    {

        lbd[num]=rbd[num]=1;

        len[num]=r-l+1;

        numseg[num]=2;

    }

    else if(l==r)//没有完全覆盖 且L==R  不就意味着没有东西在它上面么

    {

        lbd[num]=rbd[num]=numseg[num]=len[num]=0;

    }

    else

    {

        lbd[num]=lbd[num<<1];

        rbd[num]=rbd[num<<1|1];

        len[num]=len[num<<1]+len[num<<1|1];

        numseg[num]=numseg[num<<1] + numseg[num<<1|1];

        if(rbd[num<<1] && lbd[num<<1|1])numseg[num]-=2;//重合

    }

}

void update(int num,int s,int e,int l,int r,int val)

{

    if(l<=s && r>=e)

    {

        cnt[num]+=val;

        pushup(num,s,e);

        return;

    }

    int mid=(s+e)>>1;

    if(l<=mid)update(num<<1,s,mid,l,r,val);

    if(r>mid)update(num<<1|1,mid+1,e,l,r,val);

    pushup(num,s,e);

}

int main()

{

    int n;

    while(scanf("%d",&n)!=EOF)

    {

        int lmost=10000,rmost=-10000;

        int m=0;

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

        {

            int a,b,c,d;

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

            lmost=min(lmost,a);

            rmost=max(rmost,c);

            L[m].s=a;L[m].e=c;L[m].h=b;L[m++].type=1;

            L[m].s=a;L[m].e=c;L[m].h=d;L[m++].type=-1;

        }

        sort(L,L+m,cmp);

        int ans=0;

        int last=0;//记录更新之前的X周的覆盖区域

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

        {

            if(L[i].s<L[i].e)update(1,lmost,rmost-1,L[i].s,L[i].e-1,L[i].type);

            ans+=numseg[1]*(L[i+1].h-L[i].h);//计算竖直方向的长度

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

            last = len[1];

        }

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

    }

}