hdu 3642 Get The Treasury (三維的掃描線)

題目大意：

給出N個立方體。

求一個三維空間中被包圍三次的空間的體積之和。

思路分析：

發現Z的范圍很小。那麼我們可以枚舉Z軸，然後對 x y做掃描線。

而且不用枚舉所有的Z ，只需要將Z離散化之後枚舉。

#include 
#include 
#include 
#include 
#define maxn 2222
#define debug puts("fuck!")
#define lson num<<1,s,mid
#define rson num<<1|1,mid+1,e
typedef long long LL;
using namespace std;

inline void scanf_(int &num){
    char in;
    bool neg=false;
    while(((in=getchar()) > '9' || in<'0') && in!='-') ;
    if(in=='-'){
        neg=true;
        while((in=getchar()) >'9' || in<'0');
    }
    num=in-'0';
    while(in=getchar(),in>='0'&&in<='9')
        num*=10,num+=in-'0';
    if(neg)
        num=0-num;
}

struct node
{
    int x1,y1,z1;
    int x2,y2,z2;
    void scan()
    {
        scanf_(x1);
        scanf_(y1);
        scanf_(z1);
        scanf_(x2);
        scanf_(y2);
        scanf_(z2);
    }
}cube[maxn];

struct line
{
    int s,e,h,type;
    bool operator < (const line &cmp)const
    {
        return h=3)
        {
            len[num][3]=len[num][0];
            len[num][1]=len[num][2]=0;
        }
        else if(cov[num]==2)
        {
            if(s==e)
            {
                len[num][1]=len[num][3]=0;
                len[num][2]=len[num][0];
            }
            else
            {
                len[num][3]=len[num<<1][3]+len[num<<1|1][3]+len[num<<1][2]+len[num<<1|1][2]
                            +len[num<<1][1]+len[num<<1|1][1];
                len[num][2]=len[num][0]-len[num][3];
                len[num][1]=0;
            }
        }
        else if(cov[num]==1)
        {
            if(s==e)
            {
                len[num][1]=len[num][0];
                len[num][2]=len[num][3]=0;
            }
            else {
                len[num][3]=len[num<<1][3]+len[num<<1|1][3]+len[num<<1][2]+len[num<<1|1][2];
                len[num][2]=len[num<<1][1]+len[num<<1|1][1];
                len[num][1]=len[num][0]-len[num][2]-len[num][3];
            }
        }
        else
        {
            len[num][3]=len[num<<1][3]+len[num<<1|1][3];
            len[num][2]=len[num<<1][2]+len[num<<1|1][2];
            len[num][1]=len[num<<1][1]+len[num<<1|1][1];
        }
}
void build(int num,int s,int e)
{
    len[num][0]=x[e+1]-x[s];
    len[num][1]=len[num][2]=len[num][3]=0;
    cov[num]=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]>=3)
        {
            len[num][3]=len[num][0];
            len[num][1]=len[num][2]=0;
        }
        else if(cov[num]==2)
        {
            if(s==e)
            {
                len[num][1]=len[num][3]=0;
                len[num][2]=len[num][0];
            }
            else
            {
                len[num][3]=len[num<<1][3]+len[num<<1|1][3]+len[num<<1][2]+len[num<<1|1][2]
                            +len[num<<1][1]+len[num<<1|1][1];
                len[num][2]=len[num][0]-len[num][3];
                len[num][1]=0;
            }
        }
        else if(cov[num]==1)
        {
            if(s==e)
            {
                len[num][1]=len[num][0];
                len[num][2]=len[num][3]=0;
            }
            else {
                len[num][3]=len[num<<1][3]+len[num<<1|1][3]+len[num<<1][2]+len[num<<1|1][2];
                len[num][2]=len[num<<1][1]+len[num<<1|1][1];
                len[num][1]=len[num][0]-len[num][2]-len[num][3];
            }
        }
        else
        {
            len[num][3]=len[num<<1][3]+len[num<<1|1][3];
            len[num][2]=len[num<<1][2]+len[num<<1|1][2];
            len[num][1]=len[num<<1][1]+len[num<<1|1][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);
}

void solve(int kase)
{
    build(1,0,cntx-2);

    LL ans=0;
    for(int i=0;iz[i])
            {
                scline[cnt].s=cube[j].x1;
                scline[cnt].e=cube[j].x2;
                scline[cnt].h=cube[j].y1;
                scline[cnt++].type=1;

                scline[cnt].s=cube[j].x1;
                scline[cnt].e=cube[j].x2;
                scline[cnt].h=cube[j].y2;
                scline[cnt++].type=-1;
            }
        }
   
        LL area=0;
        sort(scline,scline+cnt);
       
        for(int j=0;j