POJ 3667 Hotel (线段树区间合并)

最初给你n间空房，m个操作：

　　操作1 a 表示检查是否有连续的a间空房，输出最左边的空房编号，并入住a间房间。

　　操作2 a b 表示将编号为a之后的b间房间清空。

典型的区间合并问题，这位大牛讲的更清楚：http://www.cnblogs.com/yewei/archive/2012/05/05/2484471.html

代码如下：

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 using namespace std;
  5 const int MAXN = 5e4 + 5;
  6 //sum表示这个区间的最大数，lsum表示从这个区间最左边开始连续的最大数，rsum与lsum方向相反
  7 struct data {
  8     int l , r , lsum , rsum , sum , cover;
  9 }T[MAXN << 2];
 10 
 11 void build(int p , int l , int r) {
 12     int mid = (l + r) >> 1;
 13     T[p].lsum = T[p].rsum = T[p].sum = r - l + 1;
 14     T[p].cover = -1;
 15     T[p].l = l , T[p].r = r;
 16     if(l == r)
 17         return ;
 18     build(p << 1 , l , mid);
 19     build((p << 1)|1 , mid + 1 , r);
 20 }
 21 
 22 void Pushdown(int p) {
 23     if(T[p].cover != -1) {
 24         int ls = p << 1 , rs = (p << 1)|1;
 25         T[ls].cover = T[rs].cover = T[p].cover;
 26         T[ls].lsum = T[ls].rsum = T[ls].sum = T[p].cover ? 0 : T[ls].r - T[ls].l + 1;
 27         T[rs].lsum = T[rs].rsum = T[rs].sum = T[p].cover ? 0 : T[rs].r - T[rs].l + 1;
 28         T[p].cover = -1;
 29     }
 30 }
 31 
 32 void Pushup(int p) {
 33     T[p].lsum = T[p << 1].lsum;
 34     T[p].rsum = T[(p << 1)|1].rsum;
 35     if(T[p].lsum == T[p << 1].r - T[p << 1].l + 1)
 36         T[p].lsum += T[(p << 1)|1].lsum;
 37     if(T[p].rsum == T[(p << 1)|1].r - T[(p << 1)|1].l + 1)
 38         T[p].rsum += T[p << 1].rsum;
 39     int temp = max(T[(p << 1)|1].sum , T[p << 1].rsum + T[(p << 1)|1].lsum);
 40     T[p].sum = max(T[p << 1].sum , temp);
 41 }
 42 
 43 int query(int p , int len) {
 44     int mid = (T[p].l + T[p].r) >> 1;
 45     if(T[p].l == T[p].r) {
 46         return T[p].l;
 47     }
 48     Pushdown(p);
 49     if(T[p << 1].sum >= len) { //左孩子区间的最大数，优先选左孩子
 50         return query(p << 1 , len);
 51     }
 52     else if(T[p << 1].rsum + T[(p << 1)|1].lsum >= len) { //其次要是左孩子的rsum和右孩子的lsum 加起来大于len
 53         return mid - T[p << 1].rsum + 1;
 54     }
 55     else {
 56         return query((p << 1)|1 , len); //最后就是右孩子
 57     }
 58 }
 59 
 60 void updata(int p , int l , int r , int flag) {
 61     int mid = (T[p].l + T[p].r) >> 1;
 62     if(T[p].l == l && T[p].r == r) {
 63         T[p].sum = T[p].lsum = T[p].rsum = flag ? 0 : r - l + 1;
 64         T[p].cover = flag;
 65         return ;
 66     }
 67     Pushdown(p);
 68     if(r <= mid) {
 69         updata(p << 1 , l , r , flag);
 70     }
 71     else if(l > mid) {
 72         updata((p << 1)|1 , l , r , flag);
 73     }
 74     else {
 75         updata(p << 1 , l , mid , flag);
 76         updata((p << 1)|1 , mid + 1 , r , flag);
 77     }
 78     Pushup(p);
 79 }
 80 
 81 int main()
 82 {
 83     int n , m , choose , u , v;
 84     while(~scanf("%d %d" , &n , &m)) {
 85         build(1 , 1 , n);
 86         while(m--) {
 87             scanf("%d" , &choose);
 88             if(choose == 1) {
 89                 scanf("%d" , &u);
 90                 if(T[1].sum < u)
 91                     printf("0
");
 92                 else {
 93                     int pos = query(1 , u);
 94                     printf("%d
" , pos);
 95                     updata(1 , pos , pos + u - 1 , 1);
 96                 }
 97             }
 98             else {
 99                 scanf("%d %d" , &u , &v);
100                 updata(1 , u , min(u + v - 1 , n) , 0);
101             }
102         }
103     }
104     return 0;
105 }