Smiling & Weeping

　　　　　　　　　  　　---- 在世人中间不愿渴死的人，必须学会从一切杯子里痛饮；

　　　　　　　　　　  　　　在世人中间要保持清洁的人，必须懂得用脏水也可以洗身。

题目链接：Problem - 3642 (hdu.edu.cn)

思路：扫描线

Talk is cheap , show me the code

  1 #include<bits/stdc++.h> // 在hdu提交的话，头文件要改一下
  2 using namespace std;
  3 #define ls(p) p<<1
  4 #define rs(p) p<<1|1
  5 const int N = 100010;
  6 typedef long long ll;
  7 int tag[N] , length[N][3];
  8 int xx[N] , zz[N];
  9 struct ScanLine{
 10     int y;
 11     int right_x,left_x;
 12     int inout;
 13     ScanLine(){}
 14     ScanLine(int y,int x2,int x1,int io):
 15     y(y) , right_x(x2) , left_x(x1) , inout(io){}
 16 }line[N];
 17 struct data{
 18     int x1,x2,y1,y2,z1,z2;
 19 }cube[N];
 20 bool cmp(ScanLine a , ScanLine b){ return a.y<b.y; }
 21 void push_up(int p , int pl , int pr){
 22     if(tag[p] > 2){
 23         length[p][2] = xx[pr]-xx[pl];
 24         length[p][0] = length[p][1] = 0;
 25         return ;
 26     }
 27     else if(tag[p] == 2){
 28         if(pl+1==pr){
 29             length[p][1] = xx[pr]-xx[pl];
 30             length[p][2] = length[p][0] = 0;
 31             return ;
 32         }else{
 33             length[p][2] = length[ls(p)][2]+length[rs(p)][2]+length[ls(p)][1]+length[rs(p)][1]+length[ls(p)][0]+length[rs(p)][0];
 34             length[p][1] = xx[pr]-xx[pl]-length[p][2];
 35             length[p][0] = 0;
 36         }
 37     }
 38     else if(tag[p] == 1){
 39         if(pl+1==pr){
 40             length[p][0] = xx[pr]-xx[pl];
 41             length[p][1]=length[p][2]=0;
 42             return ;
 43         }
 44         else{
 45             length[p][2] = length[ls(p)][2]+length[rs(p)][2]+length[ls(p)][1]+length[rs(p)][1];
 46             length[p][1] = length[ls(p)][0]+length[rs(p)][0];
 47             length[p][0] = xx[pr]-xx[pl]-length[p][1]-length[p][2];
 48         }
 49     }
 50     else{
 51         if(pl+1 == pr){
 52             length[p][0]=length[p][1]=length[p][2]=0;
 53             return ;
 54         }
 55         length[p][2] = length[ls(p)][2]+length[rs(p)][2];
 56         length[p][1] = length[ls(p)][1]+length[rs(p)][1];
 57         length[p][0] = length[ls(p)][0]+length[rs(p)][0];
 58     }
 59 }
 60 void update(int L, int R , int io,int p , int pl ,int pr){
 61     if(L <= pl && pr <= R){
 62         tag[p] += io;
 63         push_up(p,pl,pr);
 64         return ;
 65     }
 66     if(pl+1 == pr) return ;
 67     int mid = pl+pr >> 1;
 68     if(L <= mid) update(L,R,io,ls(p),pl,mid);
 69     if(R > mid)  update(L,R,io,rs(p),mid,pr);
 70     push_up(p,pl,pr);
 71 }
 72 int main()
 73 {
 74     int t,n,cnt1=0;
 75     scanf("%d",&t);
 76     while(t--){
 77         scanf("%d",&n);
 78         ll ans=0;
 79         int cntx=0 , cntz=0;
 80         for(int i = 1; i <= n; i++){
 81             scanf("%d%d%d%d%d%d",&cube[i].x1,&cube[i].y1,&cube[i].z1,&cube[i].x2,&cube[i].y2,&cube[i].z2);
 82             xx[++cntx] = cube[i].x1;
 83             zz[++cntz] = cube[i].z1;
 84             xx[++cntx] = cube[i].x2;
 85             zz[++cntz] = cube[i].z2;
 86         }
 87         if(n<3){
 88             printf("Case %d: 0\n",++cnt1);
 89             continue;
 90         }
 91         sort(xx+1,xx+1+cntx);
 92         sort(zz+1,zz+1+cntz);
 93         cntx = unique(xx+1,xx+1+cntx)-(xx+1);
 94         cntz = unique(zz+1,zz+1+cntz)-(zz+1);
 95         for(int i = 1; i < cntz; i++){
 96             int tot=0;
 97             for(int j = 1; j <= n; j++){
 98                 if(cube[j].z1 <= zz[i] && zz[i] < cube[j].z2){
 99                     line[++tot].y = cube[j].y1;  line[tot].right_x=cube[j].x2; line[tot].left_x=cube[j].x1; line[tot].inout=1;
100                     line[++tot].y = cube[j].y2;  line[tot].right_x=cube[j].x2; line[tot].left_x=cube[j].x1; line[tot].inout=-1;
101                 }
102             }
103             memset(length,0,sizeof(length));
104             memset(tag,0,sizeof(tag));
105             sort(line+1,line+1+tot,cmp);
106             ll s=0;
107             for(int j = 1; j <= tot; j++){
108                 int L,R;
109                 s += 1ll*length[1][2]*(line[j].y-line[j-1].y);
110                 R = lower_bound(xx+1,xx+1+cntx,line[j].right_x)-xx;
111                 L = lower_bound(xx+1,xx+1+cntx,line[j].left_x)-xx;
112                 update(L,R,line[j].inout,1,1,cntx);
113             }
114             ans += s*(zz[i+1]-zz[i]);
115         }
116         printf("Case %d: %lld\n",++cnt1,ans);
117     }
118     return 0;
119 }

所谓无底深渊，下去，也算是前程万丈

文章到此结束，我们下次再见