HDU 1540 Tunnel Warfare

线段树点修改+区间合并
对于如何查询连续某块的端点和长度还不太熟……但是属于经典常见操作。
  1 #include <cstdio>
  2 #include <cstring>
  3 #include <cstdlib>
  4 #include <algorithm>
  5 
  6 using namespace std;
  7 
  8 #define lc rt << 1
  9 #define rc rt << 1 | 1
 10 #define lson l, m, rt << 1
 11 #define rson m + 1, r, rt << 1 | 1
 12 
 13 const int MAXN = 50002;
 14 
 15 int N, Q;
 16 int stack[MAXN];
 17 int top;
 18 int len[ MAXN << 2 ];
 19 int Llen[ MAXN << 2 ];
 20 int Rlen[ MAXN << 2 ];
 21 bool lbd[ MAXN << 2 ];
 22 bool rbd[ MAXN << 2 ];
 23 
 24 void PushUp( int rt, int l, int r, int m )
 25 {
 26     len[rt] = max( len[lc], len[rc] );
 27     if ( rbd[lc] && lbd[rc] )
 28         len[rt] = max( len[rt], Llen[rc] + Rlen[lc] );
 29 
 30     lbd[rt] = lbd[lc];
 31     rbd[rt] = rbd[rc];
 32 
 33     Llen[rt] = Llen[lc];
 34     Rlen[rt] = Rlen[rc];
 35 
 36     if ( Llen[lc] == m - l + 1 ) Llen[rt] += Llen[rc];
 37     if ( Rlen[rc] == r - m ) Rlen[rt] += Rlen[lc];
 38 
 39     return;
 40 }
 41 
 42 void build( int l, int r, int rt )
 43 {
 44     if ( l == r )
 45     {
 46         lbd[rt] = rbd[rt] = true;
 47         len[rt] = 1;
 48         Llen[rt] = Rlen[rt] = 1;
 49         return;
 50     }
 51 
 52     int m = ( l + r ) >> 1;
 53     build( lson );
 54     build( rson );
 55     PushUp( rt, l, r, m );
 56     return;
 57 }
 58 
 59 void Update( int L, int c, int l, int r, int rt )
 60 {
 61     if ( L == l && L == r )
 62     {
 63         len[rt] = Llen[rt] = Rlen[rt] = c;
 64         if ( c == 1 ) lbd[rt] = rbd[rt] = true;
 65         else lbd[rt] = rbd[rt] = false;
 66         return;
 67     }
 68 
 69     int m = ( l + r ) >> 1;
 70     if ( L <= m ) Update( L, c, lson );
 71     else Update( L, c, rson );
 72     PushUp( rt, l, r, m );
 73 
 74     return;
 75 }
 76 
 77 int Query( int L, int l, int r, int rt )
 78 {
 79     if ( l == r || !len[rt] || len[rt] == r - l + 1 ) return len[rt];
 80     int m = ( l + r ) >> 1;
 81     if ( L <= m )
 82     {
 83         if ( L > m - Rlen[lc] ) return Query( L, lson ) + Query( m + 1, rson );
 84         else return Query( L, lson );
 85     }
 86     else
 87     {
 88         if ( L < m + 1 + Llen[rc] ) return Query( m, lson ) + Query( L, rson );
 89         else return Query( L, rson );
 90     }
 91 }
 92 
 93 int main()
 94 {
 95     //freopen( "in.txt", "r", stdin );
 96     //freopen( "out.txt", "w", stdout );
 97     while ( ~scanf( "%d%d", &N, &Q ) )
 98     {
 99         build( 1, N, 1 );
100         top = 0;
101         while ( Q-- )
102         {
103             char str[4];
104             scanf( "%s", str );
105             if ( str[0] == 'R' )
106             {
107                 if ( top > 0 )
108                     Update( stack[top--], 1, 1, N, 1 );
109             }
110             else
111             {
112                 int a;
113                 scanf( "%d", &a );
114                 if ( str[0] == 'D' )
115                 {
116                     Update( a, 0, 1, N, 1 );
117                     stack[ ++top ] = a;
118                 }
119                 else
120                     printf( "%d\n", Query( a, 1, N, 1 ) );
121             }
122         }
123     }
124     return 0;
125 }