HDU3642(Get The Treasury)

链接：https://vjudge.net/problem/HDU-3642
思路：三维立方体体积并，考虑二维面积并，体积并就等于高度差*面积并。我们枚举离散化x，然后y上构造线段树，用扫描线进行。三维的话就类比了，离散化x和z，然后枚举x和z，还是在y轴上构造线段树，注意枚举两个z之间的面积并的时候，我们要先把所有在两个z范围之内的扫描线提出来，再进行扫描(这样才能知道后面是哪一个)，然后面积并再乘以z坐标之差，最后求出来的就是答案

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e4+10;
int n,q,t;

struct Line{
    int x1,y1,y2,z1,z2,k;
    Line(){}
    Line(int xx1,int yy1,int yy2,int zz1,int zz2,int kk){
        x1 = xx1;
        y1 = yy1;
        y2 = yy2;
        z1 = zz1;
        z2 = zz2;
        k = kk;
    }
    bool operator<(const Line &r){
        return x1<r.x1||(x1==r.x1&&k>r.k);
    }
}line[maxn],tmp[maxn];

int y[maxn],z[maxn];

int tag[maxn<<2],len0[maxn<<2],len1[maxn<<2],len2[maxn<<2],len3[maxn<<2];

void pushup(int o,int l,int r){//一系列更新操作，自行理解
    if(tag[o]>=3){
        len3[o] = len0[o];
        len2[o] = len1[o] = 0;
    }
    else if(tag[o]==2){
        if(l==r){
            len3[o] = len1[o] = 0;
            len2[o] = len0[o];
        }
        else{
            len3[o] = len3[o<<1] + len3[o<<1|1]+len2[o<<1]+len2[o<<1|1]+len1[o<<1]+len1[o<<1|1];
            len2[o] = len0[o] - len3[o];
            len1[o] = 0;
        }
    }
    else if(tag[o]==1){
        if(l==r){
            len1[o] = len0[o];
            len2[o] = len3[o] = 0;
        }
        else{
            len3[o] = len3[o<<1] + len3[o<<1|1] + len2[o<<1] + len2[o<<1|1];
            len2[o] = len1[o<<1] + len1[o<<1|1];
            len1[o] = len0[o] - len3[o] - len2[o];
        }
    }
    else{
        if(l==r){
            len1[o] = len2[o] = len3[o] = 0;
        }
        else{
        len3[o] = len3[o<<1] + len3[o<<1|1];
        len2[o] = len2[o<<1] + len2[o<<1|1];
        len1[o] = len1[o<<1] + len1[o<<1|1];
        }
    }
}

void build(int o,int l,int r){
  tag[o] = 0;
  len1[o] = len2[o] = len3[o] = 0;
  len0[o] = y[r] - y[l-1];
  if(l<r){
    int mid = l+r>>1;
    build(o<<1,l,mid);
    build(o<<1|1,mid+1,r);
    pushup(o,l,r);
  }
}

void update(int o,int tl,int tr,int l,int r,int v){
    if(tr<l||r<tl)return;
    if(l<=tl&&tr<=r){
    tag[o]+=v;
    pushup(o,tl,tr);
        return;
  }
  int mid = (tl+tr)>>1;
  update(o<<1,tl,mid,l,r,v);
  update(o<<1|1,mid+1,tr,l,r,v);
  pushup(o,tl,tr);
} 

int main(){
    int kase = 0;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        int cnt = 0;
        int ty = 0;
        int tz = 0;
        for(int i=0;i<n;i++){
                int a,b,c,d,e,f;
                scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&e,&f);
                line[cnt].x1 = a;
                line[cnt].y1 = b;
                line[cnt].y2 = e;
                line[cnt].z1 = c;
                line[cnt].z2 = f;
                line[cnt++].k = 1;
                line[cnt].x1 = d;
                line[cnt].y1 = b;
                line[cnt].y2 = e;
                line[cnt].z1 = c;
                line[cnt].z2 = f;
                line[cnt++].k = -1;
                y[ty++] = b;
                y[ty++] = e;
                z[tz++] = c;
                z[tz++] = f;
        }
        sort(line,line+cnt);
        sort(y,y+ty);
        sort(z,z+tz);
        ty = unique(y,y+ty) - y;
        tz = unique(z,z+tz) - z;
        long long res = 0;
        for(int i=0;i<tz-1;i++){
            int z1 = z[i];
            int z2 = z[i+1];
            build(1,1,ty);
            long long ans = 0 ;
            int now = 0;
            for(int j=0;j<cnt;j++){//先把两个z之间符合条件的扫面先提出来
                if(line[j].z1<=z1&&line[j].z2>=z2)tmp[now++] = line[j];
            }
            for(int j=0;j<now;j++){//正常二维扫描线操作
                int l = lower_bound(y,y+ty,tmp[j].y1) - y+1;
                int r = lower_bound(y,y+ty,tmp[j].y2) - y;
                update(1,1,ty,l,r,tmp[j].k);
                if(j!=now-1)ans+=1LL*(tmp[j+1].x1-tmp[j].x1)*len3[1];
            }
            res+=1LL*ans*(z2-z1);
        }
        printf("Case %d: %lld\n",++kase,res);
    }
    return  0;
}