http://www.cnblogs.com/kane0526/archive/2013/03/06/2947118.html
题目大意：给你n个立方体，求相交区域大于等于三次的体积和。
这题需要前面两题的知识
体积并
http://www.cnblogs.com/qlky/p/5759481.html
面积交：
http://www.cnblogs.com/qlky/p/5765617.html
对于面积交，另外建立len2数组表示覆盖2次的面积，len3数组表示覆盖3次及以上的面积
对于体积并，离散化x坐标是为了建树，离散化z坐标是为了节省时间。对于所有的体积范围进行面积交之和即为所求体积
#include <iostream> #include <string> #include <cstring> #include <cstdlib> #include <cstdio> #include <cmath> #include <algorithm> #include <stack> #include <queue> #include <cctype> #include <vector> #include <iterator> #include <set> #include <map> #include <sstream> using namespace std; #define mem(a,b) memset(a,b,sizeof(a)) #define pf printf #define sf scanf #define spf sprintf #define pb push_back #define debug printf("! ") #define MAXN 2000+5 #define MAX(a,b) a>b?a:b #define blank pf(" ") #define LL long long #define ALL(x) x.begin(),x.end() #define INS(x) inserter(x,x.begin()) #define pqueue priority_queue #define INF 0x3f3f3f3f #define ls (rt<<1) #define rs (rt<<1|1) int n,m; int hh[MAXN],hh2[MAXN],col[MAXN<<3],len[MAXN<<3],len2[MAXN<<3],len3[MAXN<<3]; struct node { int l,r,x,c; int z1,z2; node(){} node(int a,int b,int c,int d,int e,int f):l(a),r(b),x(c),c(d),z1(e),z2(f){} bool operator < (const node &b) const { return x<b.x; } }a[MAXN<<3],tmp[MAXN<<3]; void PushUp(int rt,int l,int r) { if(col[rt]>=3) { len[rt] = len2[rt] = len3[rt] = hh[r+1] - hh[l]; } else if(col[rt] == 2) { len[rt] = len2[rt] = hh[r+1] - hh[l]; if(l==r) len3[rt] = 0; else len3[rt] = len[ls]+len[rs]; } else if(col[rt] == 1) { len[rt] = hh[r+1] - hh[l]; if(l==r) len2[rt] = len3[rt] = 0; else { len2[rt] = len[ls]+len[rs]; len3[rt] = len2[ls]+len2[rs]; } } else if(l==r) len[rt] = len2[rt] = len3[rt] = 0; else { len[rt] = len[ls]+len[rs]; len2[rt] = len2[ls]+len2[rs]; len3[rt] = len3[ls]+len3[rs]; } } void update(int val,int L,int R,int l,int r,int rt) { if(L<=l && r<=R) { col[rt] += val; PushUp(rt,l,r); return; } int mid = (l+r)>>1; if(L <= mid) update(val,L,R,l,mid,ls); if(R > mid) update(val,L,R,mid+1,r,rs); PushUp(rt,l,r); } int main() { int n,i,j,t,kase=1; sf("%d",&t); while(t--) { int v=0; sf("%d",&n); LL ans = 0; for(i=1;i<=n;i++) { int x1,x2,y1,y2; int z1,z2; sf("%d%d%d%d%d%d",&x1,&y1,&z1,&x2,&y2,&z2); hh[++v]=y1; hh2[v]=z1; a[v]=node(y1,y2,x1,1,z1,z2); hh[++v]=y2; hh2[v]=z2; a[v]=node(y1,y2,x2,-1,z1,z2); } sort(hh+1,hh+1+v); sort(hh2+1,hh2+1+v); sort(a+1,a+1+v); int d=1,d2=1; for(i=2;i<=v;i++) if(hh[i]!=hh[i-1]) hh[++d]=hh[i]; for(i=2;i<=v;i++) if(hh2[i]!=hh2[i-1]) hh2[++d2]=hh2[i]; int ct =0; for(j=1;j<=d2-1;j++) { ct=0; for(i=1;i<=v;i++) if(a[i].z1<=hh2[j] && hh2[j]< a[i].z2) tmp[ct++]=a[i]; mem(col,0); mem(len,0); mem(len2,0); mem(len3,0); for(i=0;i<ct-1;i++) { int l = lower_bound(hh+1,hh+d,tmp[i].l)-hh; int r = lower_bound(hh+1,hh+d,tmp[i].r)-hh-1; if(l<=r) update(tmp[i].c,l,r,1,d,1); //pf("t%d %d %d %d %d ",len3[1],hh2[j+1],hh2[j],tmp[i+1].x,tmp[i].x); ans+=(LL)len3[1]*(LL)(hh2[j+1]-hh2[j])*(tmp[i+1].x-tmp[i].x); //pf("t%d ",len3[1]); } } pf("Case %d: %I64d ",kase++,ans); } return 0; }