poj 3667 线段树

线段树区间合并，这题写起来还是有点麻烦的，又需要lazy标记，又需要区间合并，不过还是1A，多写数据结构的题目果真能锻炼代码能力。
  1 #include <iostream>
  2 #include <cstring>
  3 #include <cstdio>
  4 using namespace std;
  5 
  6 const int N = 50001;
  7 
  8 struct Node 
  9 {
 10     int l, r, lazy;
 11     int len, llen, rlen;
 12 } node[N << 2];
 13 
 14 void build( int i, int l, int r )
 15 {
 16     node[i].l = l, node[i].r = r;
 17     node[i].lazy = -1;
 18     node[i].len = node[i].llen = node[i].rlen = r - l + 1;
 19     if ( l == r ) return ;
 20     int mid = ( l + r ) >> 1;
 21     build( i << 1, l, mid );
 22     build( i << 1 | 1, mid + 1, r );
 23 }
 24 
 25 void pushup( int i )
 26 {
 27     int lc = i << 1, rc = lc | 1;
 28     node[i].llen = node[lc].llen;
 29     if ( node[lc].len == node[lc].r - node[lc].l + 1 )
 30     {
 31         node[i].llen += node[rc].llen;
 32     }
 33     node[i].rlen = node[rc].rlen;
 34     if ( node[rc].len == node[rc].r - node[rc].l + 1 )
 35     {
 36         node[i].rlen += node[lc].rlen;
 37     }
 38     node[i].len = max( node[lc].len, node[rc].len );
 39     node[i].len = max( node[i].len, node[lc].rlen + node[rc].llen );
 40 }
 41 
 42 void pushdown( int i )
 43 {
 44     if ( node[i].lazy == -1 ) return ;
 45     int lc = i << 1, rc = lc | 1;
 46     node[lc].lazy = node[rc].lazy = node[i].lazy;
 47     if ( node[i].lazy == 0 )
 48     {
 49         node[lc].len = node[lc].llen = node[lc].rlen = node[lc].r - node[lc].l + 1;
 50         node[rc].len = node[rc].llen = node[rc].rlen = node[rc].r - node[rc].l + 1;
 51     }
 52     else
 53     {
 54         node[lc].len = node[lc].llen = node[lc].rlen = 0;
 55         node[rc].len = node[rc].llen = node[rc].rlen = 0;
 56     }
 57     node[i].lazy = -1;
 58 }
 59 
 60 void update( int i, int l, int r, int c )
 61 {
 62     if ( node[i].l == l && node[i].r == r )
 63     {
 64         node[i].lazy = c;
 65         if ( c == 0 )
 66         {
 67             node[i].len = node[i].llen = node[i].rlen = r - l + 1;
 68         }
 69         else
 70         {
 71             node[i].len = node[i].llen = node[i].rlen = 0;
 72         }
 73         return ;
 74     }
 75     pushdown(i);
 76     int mid = ( node[i].l + node[i].r ) >> 1;
 77     if ( r <= mid )
 78     {
 79         update( i << 1, l, r, c );
 80     }
 81     else if ( l > mid )
 82     {
 83         update( i << 1 | 1, l, r, c );
 84     }
 85     else
 86     {
 87         update( i << 1, l, mid, c );
 88         update( i << 1 | 1, mid + 1, r, c );
 89     }
 90     pushup(i);
 91 }
 92 
 93 int query( int i, int d )
 94 {
 95     if ( node[i].l == node[i].r ) return node[i].l;
 96     pushdown(i);
 97     int lc = i << 1, rc = lc | 1;
 98     if ( node[lc].len >= d )
 99     {
100         return query( lc, d );
101     }
102     else if ( node[lc].rlen + node[rc].llen >= d )
103     {
104         return node[lc].r - node[lc].rlen + 1;
105     }
106     else
107     {
108         return query( rc, d );
109     }
110 }
111 
112 int main ()
113 {
114     int n, m;
115     while ( scanf("%d%d", &n, &m) != EOF )
116     {
117         build( 1, 1, n );
118         int op, x, y;
119         while ( m-- )
120         {
121             scanf("%d", &op);
122             if ( op == 1 )
123             {
124                 int d;
125                 scanf("%d", &d);
126                 if ( node[1].len < d )
127                 {
128                     printf("0
");
129                     continue;
130                 }
131                 x = query( 1, d );
132                 printf("%d
", x);
133                 y = x + d - 1;
134                 update( 1, x, y, 1 );
135             }
136             else
137             {
138                 scanf("%d%d", &x, &y);
139                 y += x - 1;
140                 update( 1, x, y, 0 );
141             }
142         }
143     }
144     return 0;
145 }