http://acm.hdu.edu.cn/showproblem.php?pid=3642
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
#include<cstring> #include<algorithm> #include<cstdio> using namespace std; #define N 1001 #define lc k<<1,l,mid #define rc k<<1|1,mid+1,r struct node { int l,r,h,f; bool operator < (node p)const { return h<p.h; } }a[N<<1]; struct edge { int x,xx,y,yy,z,zz; }b[N]; int sum1[N<<3],sum2[N<<3],sum3[N<<3],f[N<<3],has[N<<1],has2[N<<1]; long long ans; int n,cnt,opl,opr,w; void up(int k,int l,int r) { if(f[k]>=3) sum3[k]=has2[r+1]-has2[l]; else if(f[k]==2) { sum3[k]=sum1[k<<1]+sum1[k<<1|1]; sum2[k]=has2[r+1]-has2[l]; } else if(f[k]==1) { sum3[k]=sum2[k<<1]+sum2[k<<1|1]; sum2[k]=sum1[k<<1]+sum1[k<<1|1]; sum1[k]=has2[r+1]-has2[l]; } else { sum3[k]=sum3[k<<1]+sum3[k<<1|1]; sum2[k]=sum2[k<<1]+sum2[k<<1|1]; sum1[k]=sum1[k<<1]+sum1[k<<1|1]; } } void change(int k,int l,int r) { if(opl<=l && r<=opr) { f[k]+=w; up(k,l,r); return; } int mid=l+r>>1; if(opl<=mid) change(lc); if(opr>mid) change(rc); up(k,l,r); } int main() { int T; scanf("%d",&T); for(int t=1;t<=T;t++) { ans=0; cnt=0; scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d%d%d%d%d%d",&b[i].x,&b[i].y,&b[i].z,&b[i].xx,&b[i].yy,&b[i].zz); has[i*2-1]=b[i].z; has[i*2]=b[i].zz; } sort(has+1,has+2*n+1); cnt=unique(has+1,has+2*n+1)-(has+1); for(int i=1;i<cnt;i++) { int sz=0; for(int j=1;j<=n;j++) if(b[j].z<=has[i] && b[j].zz>=has[i+1]) { a[++sz].l=b[j].x; a[sz].r=b[j].xx; a[sz].h=b[j].y; a[sz].f=1; a[++sz].l=b[j].x; a[sz].r=b[j].xx; a[sz].h=b[j].yy; a[sz].f=-1; has2[sz-1]=b[j].x; has2[sz]=b[j].xx; } sort(has2+1,has2+sz+1); int m=unique(has2+1,has2+sz+1)-(has2+1); sort(a+1,a+sz+1); memset(sum1,0,sizeof(sum1)); memset(sum2,0,sizeof(sum2)); memset(sum3,0,sizeof(sum3)); for(int j=1;j<=sz;j++) { opl=lower_bound(has2+1,has2+m+1,a[j].l)-has2; opr=lower_bound(has2+1,has2+m+1,a[j].r)-has2-1; w=a[j].f; change(1,1,m); ans+=1ll*sum3[1]*(a[j+1].h-a[j].h)*(has[i+1]-has[i]); } } printf("Case %d: %I64d\n",t,ans); } }
原文:http://www.cnblogs.com/TheRoadToTheGold/p/7141987.html