【HDU】3642 Get The Treasury

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 typedef __int64 LL;
  5 using namespace std;
  6 #define MAXN 1010
  7 struct Point
  8 {
  9     int x,y,z;
 10     void Input()
 11     {
 12         scanf("%d%d%d",&x,&y,&z);
 13     }
 14 };
 15 struct Rectangle
 16 {
 17     Point a,b;
 18 };
 19 struct Seg
 20 {
 21     int left,right,high,flag;
 22     friend bool operator<(Seg a,Seg b)
 23     {
 24         if(a.high==b.high)
 25             return a.flag<b.flag;
 26         return a.high<b.high;
 27     }
 28 };
 29 struct node
 30 {
 31     int cover,one,two,more;
 32 };
 33 node tree[MAXN<<3];
 34 Rectangle r[MAXN];
 35 Seg s[MAXN<<1];
 36 int X[MAXN<<1];
 37 int Z[MAXN<<1];
 38 inline void PushUp(int L,int R,int rt)
 39 {
 40     if(tree[rt].cover>2)
 41         tree[rt].more=tree[rt].two=tree[rt].one=X[R+1]-X[L];
 42     else if(tree[rt].cover==2)
 43     {
 44         tree[rt].one=tree[rt].two=X[R+1]-X[L];
 45         if(L==R)
 46             tree[rt].more=0;
 47         else
 48             tree[rt].more=tree[rt<<1].one+tree[rt<<1|1].one;
 49     }
 50     else if(tree[rt].cover==1)
 51     {
 52         tree[rt].one=X[R+1]-X[L];
 53         if(L==R)
 54             tree[rt].two=tree[rt].more=0;
 55         else
 56         {
 57             tree[rt].two=tree[rt<<1].one+tree[rt<<1|1].one;
 58             tree[rt].more=tree[rt<<1].two+tree[rt<<1|1].two;
 59         }
 60     }
 61     else
 62     {
 63         if(L==R)
 64             tree[rt].more=tree[rt].two=tree[rt].one=0;
 65         else
 66         {
 67             tree[rt].more=tree[rt<<1].more+tree[rt<<1|1].more;
 68             tree[rt].one=tree[rt<<1].one+tree[rt<<1|1].one;
 69             tree[rt].two=tree[rt<<1].two+tree[rt<<1|1].two;
 70         }
 71     }
 72 }
 73 void Update(int x,int y,int flag,int L,int R,int rt)
 74 {
 75     if(x<=L&&R<=y)
 76     {
 77         tree[rt].cover+=flag;
 78         PushUp(L,R,rt);
 79     }
 80     else
 81     {
 82         int mid=(L+R)>>1;
 83         if(x<=mid)
 84             Update(x,y,flag,L,mid,rt<<1);
 85         if(y>mid)
 86             Update(x,y,flag,mid+1,R,rt<<1|1);
 87         PushUp(L,R,rt);
 88     }
 89 }
 90 int main()
 91 {
 92     LL ans,temp;
 93     int t,n,i,j,nx,nz,cnt,x,y,ca=1;
 94     scanf("%d",&t);
 95     while(t--)
 96     {
 97         scanf("%d",&n);
 98         for(nx=nz=i=0;i<n;i++)
 99         {
100             r[i].a.Input();
101             r[i].b.Input();
102             X[nx++]=r[i].a.x;
103             X[nx++]=r[i].b.x;
104             Z[nz++]=r[i].a.z;
105             Z[nz++]=r[i].b.z;
106         }
107         sort(X,X+nx);
108         sort(Z,Z+nz);
109         nx=unique(X,X+nx)-X;
110         nz=unique(Z,Z+nz)-Z;
111         ans=0;
112         memset(tree,0,sizeof(tree));
113         for(i=1;i<nz;i++)
114         {
115             for(cnt=j=0;j<n;j++)
116             {
117                 if(r[j].a.z<=Z[i-1]&&Z[i]<=r[j].b.z)
118                 {
119                     s[cnt].left=r[j].a.x;
120                     s[cnt].right=r[j].b.x;
121                     s[cnt].high=r[j].a.y;
122                     s[cnt++].flag=1;
123                     s[cnt].left=r[j].a.x;
124                     s[cnt].right=r[j].b.x;
125                     s[cnt].high=r[j].b.y;
126                     s[cnt++].flag=-1;
127                 }
128             }
129             sort(s,s+cnt);
130             for(temp=j=0;j<cnt;j++)
131             {
132                 x=lower_bound(X,X+nx,s[j].left)-X;
133                 y=lower_bound(X,X+nx,s[j].right)-X;
134                 Update(x,y-1,s[j].flag,0,nx-2,1);
135                 if(j+1<cnt)
136                     temp+=(LL)(s[j+1].high-s[j].high)*tree[1].more;
137             }
138             ans+=temp*(Z[i]-Z[i-1]);
139         }
140         printf("Case %d: %I64d\n",ca++,ans);
141     }
142     return 0;
143 }
新博客：www.zhixiangli.com