Codeforces Beta Round #35 (Div. 2) E. Parade(扫描线)

只要会做，周长并，这题肯定有思路。
有个小地方敲错了，细心啊，扫描线，有一段时间没写过了，还有注意排序的问题，很重要。
  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <vector>
  5 #include <cmath>
  6 #include <algorithm>
  7 using namespace std;
  8 #define LL __int64
  9 #define lson l,m,rt<<1
 10 #define rson m+1,r,rt<<1|1
 11 int que[300000];
 12 int sum[4*300000];
 13 int cnt[4*300000];
 14 int ax[1000101],ay[1000101];
 15 struct node
 16 {
 17     int h,x,c;
 18     node(){}
 19     node(int a,int b,int c):h(a),x(b),c(c){}
 20     bool operator < (const node &S)const
 21     {
 22         if(x == S.x)
 23         {
 24             if(c != S.c)
 25             return c > S.c;
 26             else if(c == 1)
 27             return h > S.h;
 28             else if(c == -1)
 29             return h < S.h;
 30         }
 31         return x < S.x;
 32     }
 33 }mat[200101];
 34 void pushup(int rt,int l,int r)
 35 {
 36     if(cnt[rt])
 37     sum[rt] = que[r+1] - que[l];
 38     else if(l == r)
 39     sum[rt] = 0;
 40     else
 41     sum[rt] = sum[rt<<1] + sum[rt<<1|1];
 42 }
 43 void update(int L,int R,int c,int l,int r,int rt)
 44 {
 45     int m;
 46     if(L <= l&&r <= R)
 47     {
 48         cnt[rt] += c;
 49         pushup(rt,l,r);
 50         return ;
 51     }
 52     m = (l + r)>>1;
 53     if(L <= m)
 54     update(L,R,c,lson);
 55     if(R > m)
 56     update(L,R,c,rson);
 57     pushup(rt,l,r);
 58     return ;
 59 }
 60 int bin(int x,int y)
 61 {
 62     int str,end,mid;
 63     str = 0;
 64     end = y;
 65     while(str <= end)
 66     {
 67         mid = (str+end)/2;
 68         if(que[mid] == x)
 69         return mid;
 70         else if(que[mid] > x)
 71         end = mid - 1;
 72         else
 73         str = mid + 1;
 74     }
 75     return mid;
 76 }
 77 int main()
 78 {
 79     int n,i,h,l,r,num;
 80     freopen("input.txt","r",stdin);
 81     freopen("output.txt","w",stdout);
 82     scanf("%d",&n);
 83     num = 0;
 84     for(i = 0;i < n;i ++)
 85     {
 86         scanf("%d%d%d",&h,&l,&r);
 87         que[i] = h;
 88         mat[num++] = node(h,l,1);
 89         mat[num++] = node(h,r,-1);
 90     }
 91     que[n] = 0;
 92     sort(que,que+n+1);
 93     sort(mat,mat+num);
 94     int k = 1;
 95     for(i = 1;i <= n;i ++)
 96     {
 97         if(que[i] != que[i-1])
 98         que[k++] = que[i];
 99     }
100     int tn = 0,pre = 0;
101     for(i = 0;i < num;i ++)
102     {
103         l = 0;
104         r = bin(mat[i].h,k-1) - 1;
105         if(l <= r)
106         {
107             update(l,r,mat[i].c,0,k-1,1);
108         }
109         if(pre != sum[1])
110         {
111             ax[tn] = mat[i].x;
112             ay[tn++] = pre;
113             ax[tn] = mat[i].x;
114             ay[tn++] = sum[1];
115             pre = sum[1];
116         }
117     }
118     printf("%d
",tn);
119     for(i = 0;i < tn;i ++)
120     {
121         printf("%d %d
",ax[i],ay[i]);
122     }
123     return 0;
124 }