hdu 1255 覆盖的总面积 (线段树扫描线 计算两次覆盖的面积)

hdu 1255 覆盖的面积 (线段树扫描线 计算两次覆盖的面积)

思路分析：

主要函数是在pushup和更新自己的时候。

要考虑到自己覆盖了的话   那么子树上的覆盖了一层的就要多加一层。

用len 数组的第二维分别计算   这个区间的长度    覆盖一次的长度   覆盖两次的长度。

自习思考一下之间的关系。保证len[0]=len[2]+len[1];

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <map>
#define maxn 10005
#define lson num<<1,s,mid
#define rson num<<1|1,mid+1,e

using namespace std;

double y[maxn<<1];
struct node
{
    double s,e,h;
    int type;
    bool operator < (const node &cmp)const{
        return h<cmp.h;
    }
}L[maxn];

int cov[maxn<<2];
double len[maxn<<2][3];
map<double,int>mp;

void pushup(int num,int s,int e)
{
    int ls=num<<1;
    int rs=num<<1|1;
    if(cov[num]>=2)
    {
        len[num][2]=len[num][0];
        len[num][1]=0;
    }
    else if(cov[num]==1)
    {
        len[num][2]=len[ls][2]+len[rs][2]+len[ls][1]+len[rs][1];
        len[num][1]=len[num][0]-len[num][2];
    }
    else
    {
        len[num][2]=len[ls][2]+len[rs][2];
        len[num][1]=len[ls][1]+len[rs][1];
    }
}

void build(int num,int s,int e)
{
    cov[num]=0;
    len[num][0]=y[e+1]-y[s];
    len[num][1]=len[num][2]=0;
    if(s==e)
    {
        return;
    }
    int mid=(s+e)>>1;
    build(lson);
    build(rson);
}

void update(int num,int s,int e,int l,int r,int val)
{
    if(l<=s && r>=e)
    {
        cov[num]+=val;
        if(cov[num]>=2)
        {
            len[num][2]=len[num][0];
            len[num][1]=0;
        }
        else if(cov[num]==1)
        {
            int ls=num<<1;
            int rs=num<<1|1;
            if(s==e){
                len[num][2]=0;
                len[num][1]=len[num][0];
            }
            else
            {
                len[num][2]=len[ls][2]+len[rs][2]+len[ls][1]+len[rs][1];
                len[num][1]=len[num][0]-len[num][2];
            }
        }
        else
        {
            int ls=num<<1;
            int rs=num<<1|1;

            if(s==e)
            {
                len[num][2]=len[num][1]=0;
            }
            else
            {
                len[num][2]=len[ls][2]+len[rs][2];
                len[num][1]=len[ls][1]+len[rs][1];
            }
        }
        return;
    }
    int mid=(s+e)>>1;
    if(l<=mid)update(lson,l,r,val);
    if(r>mid)update(rson,l,r,val);

    pushup(num,s,e);
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n;
        scanf("%d",&n);

        int top=0;int m=0;
        for(int i=1;i<=n;i++)
        {
            double a,b,c,d;
            scanf("%lf%lf%lf%lf",&a,&b,&c,&d);
            L[top].s=a;L[top].e=c;L[top].h=b;L[top++].type=1;
            L[top].s=a;L[top].e=c;L[top].h=d;L[top++].type=-1;
            y[m++]=a;y[m++]=c;
        }
        sort(y,y+m);
        m=unique(y,y+m)-y;

        for(int i=0;i<m;i++)
        {
            mp[y[i]]=i;
        }
        sort(L,L+top);


        build(1,0,m-2);

        double ans=0.0;

        for(int i=0;i<top-1;i++)
        {
            int l=mp[L[i].s];
            int r=mp[L[i].e];
            if(l<=r)update(1,0,m-2,l,r-1,L[i].type);
            ans+=len[1][2]*(L[i+1].h-L[i].h);
        }
        printf("%.2lf\n",ans);
    }
    return 0;
}