hdu-3642--Get The Treasury-线段树求面积并

求空间中叠加3次及3次以上的体积。

由于|z|<=500.所以直接把z轴剥离出来1000层。

然后对于每一层进行线段树求面积并。

#include<stdio.h>

#include<iostream>

#include<stdlib.h>

#include<string.h>

#include<algorithm>

#include<vector>

#include<math.h>

#include<map>

#pragma comment(linker, "/STACK:1024000000,1024000000")

using namespace std;

#define maxn 1100

#define mem(a,b) (memset(a),b,sizeof(a))

#define lmin 1

#define rmax len

#define lson l,(l+r)/2,rt<<1

#define rson (l+r)/2+1,r,rt<<1|1

#define root lmin,rmax,1

#define now l,r,rt

#define int_now int l,int r,int rt

#define INF 99999999

#define LL long long

#define mod 10007

#define eps 1e-6

#define zero(x) (fabs(x)<eps?

0:x)

#define LL __int64

map<int,int>mp;

int du[maxn*2];

struct lines

{

    int x;

    int y,yy;

    int z,zz;

    int leap;

    friend bool operator <(const lines &a,const lines &b)

    {

        return a.x<b.x;

    }

} line[maxn*2];

int num[maxn*4*2];

int sum[maxn*4*2];

int kum[maxn*4*2];

int cover[maxn*4*2];

void push_down(int_now)

{

}

void push_up(int_now)

{

    int len=du[r+1]-du[l];

    if(cover[rt]==0)

    {

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

        sum[rt]=sum[rt<<1]+sum[rt<<1|1];

        kum[rt]=kum[rt<<1]+kum[rt<<1|1];

    }

    if(cover[rt]==1)

    {

        num[rt]=len;

        sum[rt]=num[rt<<1]+num[rt<<1|1];

        kum[rt]=sum[rt<<1]+sum[rt<<1|1];

    }

    if(cover[rt]==2)

    {

        num[rt]=len;

        sum[rt]=len;

        kum[rt]=num[rt<<1]+num[rt<<1|1];

    }

    if(cover[rt]>=3)

    {

        num[rt]=len;

        sum[rt]=len;

        kum[rt]=len;

    }

}

void creat()

{

    memset(cover,0,sizeof(cover));

    memset(num,0,sizeof(num));

    memset(sum,0,sizeof(sum));

    memset(kum,0,sizeof(kum));

}

void updata(int ll,int rr,int x,int_now)

{

    if(ll>r||rr<l)return;

    if(ll<=l&&rr>=r)

    {

        cover[rt]+=x;

        push_up(now);

        return;

    }

    updata(ll,rr,x,lson);

    updata(ll,rr,x,rson);

    push_up(now);

}

int main()

{

    int T,cas;

    scanf("%d",&T);

    cas=0;

    while(T--)

    {

        cas++;

        int n,x,y,z,xx,yy,zz;

        mp.clear();

        scanf("%d",&n);

        LL ls=1;

        du[0]=-1000010;

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

        {

            scanf("%d%d%d%d%d%d",&x,&y,&z,&xx,&yy,&zz);

            line[i*2-1].x=x;

            line[i*2-1].y=y;

            line[i*2-1].yy=yy;

            line[i*2-1].z=z;

            line[i*2-1].zz=zz;

            line[i*2-1].leap=1;

            line[i*2].x=xx;

            line[i*2].y=y;

            line[i*2].yy=yy;

            line[i*2].z=z;

            line[i*2].zz=zz;

            line[i*2].leap=-1;

            du[ls++]=y;

            du[ls++]=yy;

        }

        sort(line+1,line+n*2+1);

        sort(du+1,du+ls);

        int len=1;

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

        {

            if(du[i]!=du[i-1])

            {

                mp[du[i]]=len;

                du[len++]=du[i];

            }

        }

        len-=2;

        LL are=0;

        int st=0;

        creat();

        for(int j=-501; j<501; j++)

        {

            st=0;

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

            {

                int l,r;

                l=mp[line[i].y];

                r=mp[line[i].yy];

                if(line[i].z>j||line[i].zz<=j)continue;

                LL x,y;

                x=(LL)kum[1];

                y=(LL)line[i].x-st;

                are+=x*y;

                updata(l,r-1,line[i].leap,root);

                st=line[i].x;

            }

        }

        printf("Case %d: %I64d\n",cas,are);

    }

    return 0;

}