POJ 1177 Picture(求周长并)

看的HH的题解。。周长有两部分组成，横着和竖着的，横着通过，sum[1] - last来计算，竖着的通过标记，记录有多少段。
  1 #include <cstdio>
  2 #include <cstring>
  3 #include <string>
  4 #include <cmath>
  5 #include <algorithm>
  6 using namespace std;
  7 #define maxn 10000
  8 #define lson l , m, rt<<1
  9 #define rson m+1, r,rt<<1|1
 10 int que[maxn*4];
 11 int sum[maxn*4];
 12 int cnt[maxn*4];
 13 bool lbd[maxn*4] , rbd[maxn*4];
 14 int numseg[maxn*4];
 15 struct node
 16 {
 17     int lx,rx,y;
 18     int s;
 19     node() {}
 20     node(int a,int b,int c,int d):lx(a),rx(b),y(c),s(d) {}
 21     bool operator < (const node &S) const
 22     {
 23         if(y == S.y) return s > S.s;
 24         return y < S.y;
 25     }
 26 } mat[maxn];
 27 int bin(int x,int n)
 28 {
 29     int str,end,mid;
 30     str = 0,end = n;
 31     while(str <= end)
 32     {
 33         mid = (str+end)/2;
 34         if(que[mid] == x)
 35             return mid;
 36         else if(que[mid] > x)
 37             end = mid - 1;
 38         else
 39             str = mid + 1;
 40     }
 41     return mid;
 42 }
 43 void pushup(int rt,int l,int r)
 44 {
 45     if(cnt[rt])
 46     {
 47         lbd[rt] = rbd[rt] = 1;
 48         sum[rt] = que[r+1] - que[l];
 49         numseg[rt] = 2;
 50     }
 51     else if (l == r)
 52     {
 53         sum[rt] = numseg[rt] = lbd[rt] = rbd[rt] = 0;
 54     }
 55     else
 56     {
 57         lbd[rt] = lbd[rt<<1];
 58         rbd[rt] = rbd[rt<<1|1];
 59         sum[rt] = sum[rt<<1] + sum[rt<<1|1];
 60         numseg[rt] = numseg[rt<<1] + numseg[rt<<1|1];
 61         if (lbd[rt<<1|1] && rbd[rt<<1]) numseg[rt] -= 2;
 62     }
 63 }
 64 void update(int L,int R,int c,int l,int r,int rt)
 65 {
 66     if(L <= l&&r <= R)
 67     {
 68         cnt[rt] += c;
 69         pushup(rt,l,r);
 70         return ;
 71     }
 72     int m = (l+r)>>1;
 73     if(L <= m)
 74         update(L,R,c,lson);
 75     if(R > m)
 76         update(L,R,c,rson);
 77     pushup(rt,l,r);
 78 }
 79 int main()
 80 {
 81     int n,num,i,l,r;
 82     int a,b,c,d;
 83     while(scanf("%d",&n)!=EOF)
 84     {
 85         if(!n) break;
 86         num = 0;
 87         for(i = 0; i < n; i ++)
 88         {
 89             scanf("%d%d%d%d",&a,&b,&c,&d);
 90             que[num] = a;
 91             mat[num ++] = node(a,c,b,1);
 92             que[num] = c;
 93             mat[num ++] = node(a,c,d,-1);
 94         }
 95         sort(que,que+num);
 96         sort(mat,mat+num);
 97         int k = 1;
 98         for(i = 1; i < num; i ++)
 99         {
100             if(que[i] != que[i-1])
101                 que[k++] = que[i];
102         }
103         int ans = 0,last = 0;
104         memset(cnt,0,sizeof(cnt));
105         memset(sum,0,sizeof(sum));
106         memset(lbd,0,sizeof(lbd));
107         memset(rbd,0,sizeof(rbd));
108         for(i = 0; i < num; i ++)
109         {
110             l = bin(mat[i].lx,k-1);
111             r = bin(mat[i].rx,k-1)-1;
112             if(l <= r)
113                 update(l,r,mat[i].s,0,k-1,1);
114             ans += numseg[1] * (mat[i+1].y - mat[i].y);
115             ans += abs(sum[1] - last);
116             last = sum[1];
117         }
118         printf("%d
",ans);
119     }
120     return 0;
121 }