POJ 2528 Mayor's posters 线段树+离散化

离散化的时候，排序后相邻点差值大于1的话需要加点。
  1 #include <cstdio>
  2 #include <cstring>
  3 #include <cstdlib>
  4 #include <algorithm>
  5 
  6 #define lson l, m, rt << 1
  7 #define rson m + 1, r, rt << 1 | 1
  8 
  9 using namespace std;
 10 
 11 const int MAXN = 42222;
 12 
 13 struct node
 14 {
 15     int id;
 16     int a, b;
 17 };
 18 
 19 int n;
 20 int flag[ ( MAXN << 2 ) << 2 ];
 21 int color[ ( MAXN << 2 ) << 2 ];
 22 int val[ MAXN << 2 ];
 23 node Q[MAXN];
 24 bool vis[ MAXN << 2 ];
 25 
 26 void PushDown( int rt )
 27 {
 28     int lc = rt << 1;
 29     int rc = rt << 1 | 1;
 30     if ( flag[rt] != -1 )
 31     {
 32         flag[lc] = flag[rc] = flag[rt];
 33         color[lc] = color[rc] = flag[rt];
 34         flag[rt] = -1;
 35     }
 36     return;
 37 }
 38 
 39 void build( int l, int r, int rt )
 40 {
 41     color[rt] = -1;
 42     flag[rt] = -1;
 43     if ( l == r ) return;
 44     int m = ( l + r ) >> 1;
 45     build(lson);
 46     build(rson);
 47     return;
 48 }
 49 
 50 void Update( int L, int R, int c, int l, int r, int rt )
 51 {
 52     if ( L <= l && r <= R )
 53     {
 54         color[rt] = flag[rt] = c;
 55         return;
 56     }
 57     PushDown(rt);
 58     int m = ( l + r ) >> 1;
 59     if ( L <= m ) Update( L ,R, c, lson );
 60     if ( R > m ) Update( L ,R, c, rson );
 61     return;
 62 }
 63 
 64 int Query( int c, int l, int r, int rt )
 65 {
 66     if ( l == c && r == c )
 67         return color[rt];
 68 
 69     PushDown( rt );
 70     int m = ( l + r ) >> 1;
 71     if ( c <= m ) return Query( c, lson );
 72     else return Query( c, rson );
 73 }
 74 
 75 int main()
 76 {
 77     int T;
 78     scanf( "%d", &T );
 79     while ( T-- )
 80     {
 81         scanf( "%d", &n );
 82         int cnt = 0;
 83         for ( int i = 0; i < n; ++i )
 84         {
 85             scanf( "%d%d", &Q[i].a, &Q[i].b );
 86             val[ cnt++ ] = Q[i].a;
 87             val[ cnt++ ] = Q[i].b;
 88             Q[i].id = i + 1;
 89         }
 90         sort( val, val + cnt );
 91 
 92         int len = cnt;
 93         for ( int i = 1; i < len; ++i )
 94         {
 95             if ( val[i] - val[i - 1] > 1 )
 96             {
 97                 val[cnt++] = val[i] - 1;
 98             }
 99         }
100 
101         sort( val, val + cnt );
102         cnt = unique( val, val + cnt ) - val;
103 
104 //        for ( int i = 0; i < cnt; ++i )
105 //            printf( "%d ", val[i] );
106 //        puts("");
107 
108         build( 0, cnt - 1, 1 );
109 
110         for ( int i = 0; i < n; ++i )
111         {
112             int left = lower_bound( val, val + cnt, Q[i].a ) - val;
113             int right = lower_bound( val, val + cnt, Q[i].b ) - val;
114             //printf( "%d %d
", left, right );
115             Update( left, right, Q[i].id, 0, cnt - 1, 1 );
116         }
117 
118         memset( vis, false, sizeof(vis) );
119         for ( int i = 0; i < cnt; ++i )
120         {
121             int ans = Query( i, 0, cnt - 1, 1 );
122             if ( ans != -1 ) vis[ans] = true;
123         }
124 
125         int ans = 0;
126         for ( int i = 1; i <= n; ++i )
127             if ( vis[i] ) ++ans;
128 
129         printf( "%d
", ans );
130     }
131     return 0;
132 }