线段树 扫描线 HDU 1828

#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<math.h>

using namespace std;

#define inf 100000000
#define MAXN 5010
#define MAXN 20010
struct edge 
{
    int l,r,h,f;  //线段的 左边 右边 高度 

}x[MAXN<<1];
struct node
{
    int l,r,len,s; // 左边 右边 现在覆盖的长度 
    bool lc,rc;    //左右端点是否覆盖
    int num;       //这个区间上多少个线段
}z[MAXN<<3];
bool cmp(edge a,edge b)
{
    return a.h<b.h;
}
void Build(int l,int r,int a)
{
    z[a].l=l;
    z[a].r=r;
    z[a].s=z[a].len=0;
    z[a].lc=z[a].rc=z[a].num=0;
    if(l==r)
        return ;
    int mid=(l+r)>>1;
    Build(l,mid,a<<1);
    Build(mid+1,r,a<<1|1);
}
void push_up(int a) //区间合并
{
    if(z[a].s)//整个都被覆盖
    {
        z[a].len=z[a].r-z[a].l+1;
        z[a].lc=z[a].rc=1;
        z[a].num=1;
    }
    else if(z[a].l==z[a].r) //单个的点
    {
        z[a].len=0;
        z[a].lc=z[a].rc=0;
        z[a].num=0;
    }
    else  //一段区间
    {
        z[a].len=z[a<<1].len+z[a<<1|1].len;
        z[a].lc=z[a<<1].lc;
        z[a].rc=z[a<<1|1].rc;
        z[a].num=z[a<<1].num+z[a<<1|1].num-(z[a<<1].rc&z[a<<1|1].lc);
    }
}
void update(int l,int r,int a1,int b1,int f,int a)
{
    if(a1<=l&&r<=b1)
    {
        z[a].s+=f;
        push_up(a);
        return ;
    }
    int mid=(l+r)>>1;
    if(a1<=mid)
        update(l,mid,a1,b1,f,a<<1);
    if(b1>mid)
        update(mid+1,r,a1,b1,f,a<<1|1);
    push_up(a);
}

int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        int x1,x2,y1,y2,mx=-inf,mn=inf;
        int cnt=0;

        for(int i=0;i<n;i++)
        {
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            mx=max(mx,max(x1,x2));//维护最小和最大
            mn=min(mn,min(x1,x2));
            x[cnt].l=x[cnt+1].l=x1;
            x[cnt].r=x[cnt+1].r=x2;
            x[cnt].h=y1;
            x[cnt+1].h=y2;
            x[cnt].f=1;
            x[cnt+1].f=-1;
            cnt+=2;
        }
        sort(x,x+cnt,cmp);   //按高度排序
        Build(mn,mx-1,1);    //这边要减一
        int last=0,ans=0;
        for(int i=0;i<cnt;i++)
        {
            update(mn,mx-1,x[i].l,x[i].r-1,x[i].f,1);
            ans+=abs(z[1].len-last);  //这次和上次覆盖的差
            ans+=(x[i+1].h-x[i].h)*2*z[1].num;//高度乘以数目
            last=z[1].len;
        }

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