参考链接 ： http://blog.csdn.net/zxy_snow/article/details/6870127
题意：给你n个立方体，求覆盖三次以上（包括三次）的区域的体积
思路：先将z坐标离散后，然后一层一层地开始扫描，计算该层中覆盖>=3次的面积，这个就同二维扫描一样，然后再用面积乘以这层的高度，
即得到该层覆盖>=3次的体积，所有层的体积加起来，即为所求。
对于每一层，只有当该层区域在扫描的线的z1,z2范围中，才将该线条插入。
其它操作就同POJ 1151 Atlantis 求矩形的面积并一样。
这里要注意的是，如果扫描的时候，是用单点更新，那么就会TLE。
后来看了网上别人的区间更新的代码，这才A了。
#include <iostream> #include <stdio.h> #include <algorithm> #include <string.h> #define lson rt<<1,L,mid #define rson rt<<1|1,mid,R /* AC 参考链接 http://blog.csdn.net/zxy_snow/article/details/6870127 题意：给你n个立方体，求覆盖三次以上（包括三次）的区域的体积 思路：先将z坐标离散后，然后一层一层地开始扫描，计算该层中覆盖>=3次的面积，这个就同二维扫描一样，然后再用面积乘以这层的高度， 即得到该层覆盖>=3次的体积，所有层的体积加起来，即为所求。 对于每一层，只有当该层区域在扫描的线的z1,z2范围中，才将该线条插入。 其它操作就同POJ 1151 Atlantis 求矩形的面积并一样。 这里要注意的是，如果扫描的时候，是用单点更新，那么就会TLE。 后来看了网上别人的区间更新代码，这才A了。 */ using namespace std; const int maxn=1005; int n; int xval[maxn*2],zval[maxn*2]; //存储x和z出现的所有值 int idx,idz; //xval和zval存储的数的个数 int hashx[maxn*2],hashz[maxn*2]; //用于离散化 int hx,hz; //x和z离散后的个数 long long ans; struct Line{ //l r：线条的横坐标左端点和右端点；y：纵坐标值 //z1 z2：线条所处的z坐标范围 int l,r,y,z1,z2; int tp; //标记，tp=1表示矩形的下边，tp=-1表示矩形的上边 bool operator<(const Line tmp)const{ return y<tmp.y; } }line[maxn*2]; struct Node{ int cnt; //该区间被覆盖的次数 /* once：该区间中被覆盖一次的线段长度 twice：该区间中被覆盖两次的线段长度 len：该区间中被覆盖>=三次的线段长度 */ long long once,twice,len; }tree[maxn<<3]; //二分搜索x坐标对应的离散值 int binarySearchx(int m){ int l=0,r=hx+1,mid; while(r-l>1){ mid=(l+r)>>1; if(hashx[mid]<=m) l=mid; else r=mid; } return l; } void build(int rt,int L,int R){ tree[rt].cnt=tree[rt].len=tree[rt].twice=tree[rt].once=0; if(L+1==R) return; int mid=(L+R)>>1; build(lson); build(rson); } /* 还是网上看了大牛们的代码，用区间查询，才AC 原本自己就直接单点更新，导致TLE。。。 */ void pushUp(int rt,int L,int R){ if(tree[rt].cnt>=3){ tree[rt].once=tree[rt].twice=0; tree[rt].len=hashx[R]-hashx[L]; } else if(tree[rt].cnt==2){ if(L+1==R){ tree[rt].once=tree[rt].len=0; tree[rt].twice=hashx[R]-hashx[L]; } else{ tree[rt].once=0; tree[rt].len=tree[rt<<1].len+tree[rt<<1|1].len+tree[rt<<1].twice+tree[rt<<1|1].twice +tree[rt<<1].once+tree[rt<<1|1].once; tree[rt].twice=hashx[R]-hashx[L]-tree[rt].len; } } else if(tree[rt].cnt==1){ if(L+1==R){ tree[rt].once=hashx[R]-hashx[L]; tree[rt].twice=tree[rt].len=0; } else{ tree[rt].len=tree[rt<<1].len+tree[rt<<1|1].len+tree[rt<<1].twice+tree[rt<<1|1].twice; tree[rt].twice=tree[rt<<1].once+tree[rt<<1|1].once; tree[rt].once=hashx[R]-hashx[L]-tree[rt].len-tree[rt].twice; } } else{ if(L+1==R){ tree[rt].len=tree[rt].once=tree[rt].twice=0; } else{ tree[rt].len=tree[rt<<1].len+tree[rt<<1|1].len; tree[rt].twice=tree[rt<<1].twice+tree[rt<<1|1].twice; tree[rt].once=tree[rt<<1].once+tree[rt<<1|1].once; } } } void update(int rt,int L,int R,int l,int r,int c){ if(l<=L&&R<=r){ tree[rt].cnt+=c; pushUp(rt,L,R); return; } int mid=(L+R)>>1; if(r<=mid) update(lson,l,r,c); else if(l>=mid) update(rson,l,r,c); else{ update(lson,l,mid,c); update(rson,mid,r,c); } pushUp(rt,L,R); } int main() { int t; int x1,y1,z1,x2,y2,z2; scanf("%d",&t); for(int q=1;q<=t;q++){ scanf("%d",&n); idx=idz=0; for(int i=1;i<=n;i++){ scanf("%d%d%d%d%d%d",&x1,&y1,&z1,&x2,&y2,&z2); line[2*i-1].l=x1;line[2*i-1].r=x2;line[2*i-1].y=y1;line[2*i-1].z1=z1;line[2*i-1].z2=z2;line[2*i-1].tp=1; line[2*i].l=x1;line[2*i].r=x2;line[2*i].y=y2;line[2*i].z1=z1;line[2*i].z2=z2;line[2*i].tp=-1; xval[++idx]=x1; xval[++idx]=x2; zval[++idz]=z1; zval[++idz]=z2; } n=n*2; sort(line+1,line+n+1); sort(xval+1,xval+idx+1); sort(zval+1,zval+idz+1); hx=hz=0; //将x坐标值离散化 hashx[++hx]=xval[1]; for(int i=2;i<=idx;i++){ if(xval[i]!=xval[i-1]) hashx[++hx]=xval[i]; } //将y坐标值离散化 hashz[++hz]=zval[1]; for(int i=2;i<=idz;i++){ if(zval[i]!=zval[i-1]) hashz[++hz]=zval[i]; } ans=0; int minz,maxz; int a,b; //一层一层地扫描 for(int i=1;i<hz;i++){ //minz和maxz表示该层所处的范围 minz=hashz[i]; maxz=hashz[i+1]; build(1,1,hx); long long s=0; //该层被覆盖>=3的面积 int last=0; //记录上一次扫描线的编号 for(int j=1;j<=n;j++){ if(line[j].z1<=minz && maxz<=line[j].z2){ s+=tree[1].len*(line[j].y-line[last].y); last=j; a=binarySearchx(line[j].l); b=binarySearchx(line[j].r); update(1,1,hx,a,b,line[j].tp); } } ans+=s*(maxz-minz); } printf("Case %d: %I64d ",q,ans); } return 0; }
后来这道题自己又做了一遍，基本上和之前的差不多，只不过离散化的时候就在原来数组的基础上进行
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <cmath> #define lson rt<<1,L,mid #define rson rt<<1|1,mid+1,R using namespace std; const int maxn=1000+5; int n,m; int cntx,idx; int cntz,idz; int hashx[maxn<<1]; int hashz[maxn<<1]; struct Line{ int y,l,r; int tp; int z1,z2; bool operator<(const Line tmp)const{ return y<tmp.y; } }line[maxn<<1]; struct Node{ int cnt; int len[4]; }tree[maxn<<3]; void build(int rt,int L,int R){ tree[rt].cnt=0; tree[rt].len[1]=tree[rt].len[2]=tree[rt].len[3]=0; if(L==R) return; int mid=(L+R)>>1; build(lson); build(rson); } void pushUp(int rt,int L,int R){ //别忘了考虑叶子节点的情况 if(tree[rt].cnt==0){ if(L==R){ tree[rt].len[1]=tree[rt].len[2]=tree[rt].len[3]=0; } else{ tree[rt].len[1]=tree[rt<<1].len[1]+tree[rt<<1|1].len[1]; tree[rt].len[2]=tree[rt<<1].len[2]+tree[rt<<1|1].len[2]; tree[rt].len[3]=tree[rt<<1].len[3]+tree[rt<<1|1].len[3]; } } else if(tree[rt].cnt==1){ if(L==R){ tree[rt].len[1]=hashx[R+1]-hashx[L]; tree[rt].len[2]=tree[rt].len[3]=0; } else{ tree[rt].len[3]=tree[rt<<1].len[2]+tree[rt<<1|1].len[2]+tree[rt<<1].len[3]+tree[rt<<1|1].len[3]; tree[rt].len[2]=tree[rt<<1].len[1]+tree[rt<<1|1].len[1]; tree[rt].len[1]=hashx[R+1]-hashx[L]-tree[rt].len[3]-tree[rt].len[2]; } } else if(tree[rt].cnt==2){ if(L==R){ tree[rt].len[2]=hashx[R+1]-hashx[L]; tree[rt].len[1]=tree[rt].len[3]=0; } else{ tree[rt].len[1]=0; tree[rt].len[3]=tree[rt<<1].len[1]+tree[rt<<1].len[2]+tree[rt<<1].len[3] +tree[rt<<1|1].len[1]+tree[rt<<1|1].len[2]+tree[rt<<1|1].len[3]; tree[rt].len[2]=hashx[R+1]-hashx[L]-tree[rt].len[3]; } } else{ tree[rt].len[1]=tree[rt].len[2]=0; tree[rt].len[3]=hashx[R+1]-hashx[L]; } } void update(int rt,int L,int R,int l,int r,int val){ if(l<=L&&R<=r){ tree[rt].cnt+=val; pushUp(rt,L,R); return; } int mid=(L+R)>>1; if(l<=mid) update(lson,l,r,val); if(r>mid) update(rson,l,r,val); pushUp(rt,L,R); } int binarySearch(int x){ int l=0,r=idx+1,mid; while(r-l>1){ mid=(l+r)>>1; if(hashx[mid]<=x) l=mid; else r=mid; } return l; } int main() { int t; int x1,y1,z1,x2,y2,z2; scanf("%d",&t); for(int q=1;q<=t;q++){ scanf("%d",&n); cntx=cntz=1; for(int i=1;i<=n;i++){ scanf("%d%d%d%d%d%d",&x1,&y1,&z1,&x2,&y2,&z2); line[2*i-1].y=y1;line[2*i-1].l=x1;line[2*i-1].r=x2; line[2*i-1].z1=z1;line[2*i-1].z2=z2;line[2*i-1].tp=1; line[2*i].y=y2;line[2*i].l=x1;line[2*i].r=x2; line[2*i].z1=z1;line[2*i].z2=z2;line[2*i].tp=-1; hashx[cntx++]=x1; hashx[cntx++]=x2; hashz[cntz++]=z1; hashz[cntz++]=z2; } n=n*2; sort(hashx+1,hashx+cntx); sort(hashz+1,hashz+cntz); idx=1; for(int i=2;i<cntx;i++){ if(hashx[i]!=hashx[i-1]){ hashx[++idx]=hashx[i]; } } idz=1; for(int i=2;i<cntz;i++){ if(hashz[i]!=hashz[i-1]) hashz[++idz]=hashz[i]; } sort(line+1,line+n+1); long long ans=0; for(int i=1;i<idz;i++){ long long area=0; int last=0; build(1,1,idx); for(int j=1;j<=n;j++){ if(line[j].z1<=hashz[i] && hashz[i+1]<=line[j].z2){ //这里乘积可能会爆int，所以要转化成long long，或者将tree[1].len定义成long long area+=(long long)tree[1].len[3]*(line[j].y-line[last].y); int a=binarySearch(line[j].l); int b=binarySearch(line[j].r)-1; update(1,1,idx,a,b,line[j].tp); last=j; } } ans+=area*(hashz[i+1]-hashz[i]); } printf("Case %d: %I64d ",q,ans); } return 0; }