题意：给你一些长方体，问你覆盖三次及以上的体积有多大
首先我们观察x轴y轴一样很大，但是z轴很小，所以我们可以枚举z轴（-500,500）,注意我们枚举的是每一段长度为一的z轴的xy轴的面积而不是点。接着就是求在这一段内的矩形面积并的变形
注意我们要首先计算，再插入线段求面积并
#include<set> #include<map> #include<queue> #include<stack> #include<cmath> #include<vector> #include<string> #include<cstdio> #include<cstring> #include<stdlib.h> #include<iostream> #include<algorithm> using namespace std; #define eps 1E-8 /*注意可能会有输出-0.000*/ #define Sgn(x) (x<-eps? -1 :x<eps? 0:1)//x为两个浮点数差的比较,注意返回整型 #define Cvs(x) (x > 0.0 ? x+eps : x-eps)//浮点数转化 #define zero(x) (((x)>0?(x):-(x))<eps)//判断是否等于0 #define mul(a,b) (a<<b) #define dir(a,b) (a>>b) typedef long long ll; typedef unsigned long long ull; const int Inf=1<<28; const double Pi=acos(-1.0); const int Mod=1e9+7; const int Max=1010; struct node { int xx1,yy1,zz1,xx2,yy2,zz2; } rec [Max]; struct nude { int xx1,xx2,yy1,cover; } lin[Max<<1]; struct nide { int cover,dp[4];//覆盖次数 此点代表值 } segtr[Max<<3]; map<int,int> mp; int mpx[Max<<1]; void Upnow(int now,int next) { segtr[now].dp[0]=segtr[next].dp[0]+segtr[next|1].dp[0]; return; } void Create(int sta,int enn,int now) { segtr[now].dp[1]=segtr[now].dp[2]=segtr[now].dp[3]=0; segtr[now].cover=0; if(sta==enn) { segtr[now].dp[0]=mpx[sta+1]-mpx[sta]; return; } int mid=dir(sta+enn,1); int next=mul(now,1); Create(sta,mid,next); Create(mid+1,enn,next|1); Upnow(now,next); return; } void Jud(int sta,int enn,int now) { int next=mul(now,1); if(segtr[now].cover>=3) { segtr[now].dp[3]=segtr[now].dp[0]; segtr[now].dp[1]=segtr[now].dp[2]=0; } else if(segtr[now].cover==2) { segtr[now].dp[1]=0; if(sta==enn) { segtr[now].dp[3]=0; } else { segtr[now].dp[3]=segtr[next].dp[1]+segtr[next|1].dp[1]+segtr[next].dp[2]+segtr[next|1].dp[2]+segtr[next].dp[3]+segtr[next|1].dp[3]; } segtr[now].dp[2]=segtr[now].dp[0]-segtr[now].dp[3]; } else if(segtr[now].cover==1) { if(sta==enn) { segtr[now].dp[2]=segtr[now].dp[3]=0; segtr[now].dp[1]=segtr[now].dp[0]; } else { segtr[now].dp[2]=segtr[next].dp[1]+segtr[next|1].dp[1]; segtr[now].dp[3]=segtr[next].dp[2]+segtr[next|1].dp[2]+segtr[next].dp[3]+segtr[next|1].dp[3]; segtr[now].dp[1]=segtr[now].dp[0]-segtr[now].dp[3]-segtr[now].dp[2]; } } else { if(sta==enn) { segtr[now].dp[1]=segtr[now].dp[2]=segtr[now].dp[3]=0; } else { segtr[now].dp[1]=segtr[next].dp[1]+segtr[next|1].dp[1]; segtr[now].dp[2]=segtr[next].dp[2]+segtr[next|1].dp[2]; segtr[now].dp[3]=segtr[next].dp[3]+segtr[next|1].dp[3]; } } return; } void Update(int sta,int enn,int now,int x,int y,int z) { if(x<=sta&&enn<=y) { segtr[now].cover+=z; Jud(sta,enn,now); return; } int mid=dir(sta+enn,1); int next=mul(now,1); if(mid>=x) Update(sta,mid,next,x,y,z); if(mid<y) Update(mid+1,enn,next|1,x,y,z); Jud(sta,enn,now); return; } bool cmp(struct nude p1,struct nude p2) { if(p1.yy1==p2.yy1) return p1.cover>p2.cover; return p1.yy1<p2.yy1; } ll Vol(int n,int cnt,int coun)//求z轴在区间内的面积三次及以上并 { if(!coun) return 0ll; ll sum=0ll; Create(1,cnt,1);//按照x轴建树 sort(lin,lin+coun,cmp);//按照y轴排序后枚举线段 Update(1,cnt,1,mp[lin[0].xx1],mp[lin[0].xx2]-1,lin[0].cover);//第一条线段不能加到总面积上 for(int i=1; i<coun; ++i) //按照y轴枚举每条线 { sum+=(ll)segtr[1].dp[3]*(lin[i].yy1-lin[i-1].yy1);//一定更新到了父节点 注意先计算 Update(1,cnt,1,mp[lin[i].xx1],mp[lin[i].xx2]-1,lin[i].cover); } return sum; } ll Solve(int n) { ll sum=0ll; for(int i=0; i<1000; ++i) //枚举所有可能的z轴 { mp.clear(); int coun=0; for(int j=0; j<n; ++j) { if(rec[j].zz1<=i&&rec[j].zz2>i)//段变点 { mp[rec[j].xx1]=1; mp[rec[j].xx2]=1; lin[coun].xx1=rec[j].xx1,lin[coun].xx2=rec[j].xx2,lin[coun].yy1=rec[j].yy1,lin[coun++].cover=1; lin[coun].xx1=rec[j].xx1,lin[coun].xx2=rec[j].xx2,lin[coun].yy1=rec[j].yy2,lin[coun++].cover=-1; } } int cnt=0; for(map<int,int>::iterator it=mp.begin(); it!=mp.end(); ++it) { it->second=++cnt;//离散化 mpx[cnt]=it->first; } mpx[cnt+1]=mpx[cnt]; sum+=Vol(n,cnt,coun); } return sum; } int main() { int t,n,coun=0; scanf("%d",&t); while(t--) { scanf("%d",&n); for(int i=0; i<n; ++i) { scanf("%d %d %d %d %d %d",&rec[i].xx1,&rec[i].yy1,&rec[i].zz1,&rec[i].xx2,&rec[i].yy2,&rec[i].zz2); rec[i].zz1+=500,rec[i].zz2+=500; } printf("Case %d: %I64d ",++coun,Solve(n)); } return 0; }