POJ 3667 Hotel 线段树处理区间信息

题目大意：
Hotel里有N个房间，初始全为空，有两种操作
第一种找到序列中最左端的，满足连续1的个数>=d个的位置，并把这些1变成0
第二种是区间修改L,R变成1
题目分析：
就是区间合并问题，不过有些麻烦
 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6 #define maxn 50010
 7 #define lson l, m, rt << 1
 8 #define rson m + 1, r, rt << 1 | 1
 9 using namespace std;
10 struct SegTree{
11     int l,r;
12     int mi,lsum,rsum,sum,res,p;
13 }tr[maxn << 2];
14 int col[maxn << 2];
15 int n,Q;
16 inline void pushup(int rt){
17     tr[rt].sum = tr[rt << 1].sum + tr[rt << 1 | 1].sum;
18     tr[rt].lsum = tr[rt << 1].lsum + (tr[rt << 1].r - tr[rt << 1].l + 1 == tr[rt << 1].sum ? tr[rt << 1 | 1].lsum : 0);
19     tr[rt].rsum = tr[rt << 1 | 1].rsum + (tr[rt << 1 | 1].r - tr[rt << 1 | 1].l + 1 == tr[rt << 1 | 1].sum ? tr[rt << 1].rsum : 0);
20     tr[rt].mi = max(max(tr[rt << 1].mi, tr[rt << 1 | 1].mi), tr[rt << 1].rsum + tr[rt << 1 | 1].lsum);     
21     tr[rt].res = tr[rt << 1].rsum + tr[rt << 1 | 1].lsum;
22     tr[rt].p = tr[rt << 1].r - tr[rt << 1].rsum + 1;
23 }
24 inline void pushdown(int rt){
25     if(col[rt] != -1){
26         col[rt << 1] = col[rt << 1 | 1] = col[rt];
27         tr[rt << 1].lsum = tr[rt << 1].rsum = tr[rt << 1].sum = tr[rt << 1].mi = tr[rt << 1].res = (tr[rt << 1].r - tr[rt << 1].l + 1) * col[rt];
28         tr[rt << 1].p = tr[rt << 1].l;
29         tr[rt << 1 | 1].lsum = tr[rt << 1 | 1].rsum = tr[rt << 1 | 1].sum = tr[rt << 1 | 1].mi = tr[rt << 1 | 1].res = (tr[rt << 1 | 1].r - tr[rt << 1 | 1].l + 1) * col[rt];
30         tr[rt << 1 | 1].p = tr[rt << 1 | 1].l;
31         col[rt] = -1;
32     }
33 }
34 inline void build(int l,int r,int rt){
35     tr[rt].l = l, tr[rt].r = r;
36     tr[rt].lsum = tr[rt].rsum = tr[rt].sum = tr[rt].sum = 1;
37     col[rt] = -1;
38     if(l == r){
39         return;
40     }
41     int m = (l + r) >> 1;
42     build(lson);
43     build(rson);
44     pushup(rt);
45 }
46 inline void Query(int val,int l,int r,int rt,int &p){
47     if(tr[rt].lsum >= val){
48         p = tr[rt].l;
49         return;
50     }
51     pushdown(rt);
52     int m = (l + r) >> 1;
53     if(tr[rt << 1].mi >= val) Query(val, lson, p);
54     else if(tr[rt].res >= val) p = tr[rt].p;
55     else if(tr[rt << 1 | 1].mi >= val) Query(val, rson, p);
56     //pushup(rt);
57 }
58 inline void update(int L,int R,int c,int l,int r,int rt){
59     if(l >= L && r <= R){
60         tr[rt].lsum =tr[rt].res = tr[rt].rsum = tr[rt].sum = tr[rt].mi = (tr[rt].r - tr[rt].l + 1) * c;
61         tr[rt].p = tr[rt].l;
62         col[rt] = c; 
63         return;
64     }
65     pushdown(rt);
66     int m = (l + r) >> 1;
67     if(L <= m) update(L,R,c,lson);
68     if(R  > m) update(L,R,c,rson);
69     pushup(rt);
70 }
71 int main(){
72     std::ios::sync_with_stdio(false);
73     int opt, x, d, pos;
74     cin >> n >> Q;
75     build(1, n, 1);
76     for(int i = 1; i <= Q; i ++){
77         cin >> opt;
78         if(opt == 1){
79             cin >> d;
80             if(tr[1].mi < d){
81                 cout << 0 << endl;
82             }
83             else{
84                 Query(d,1,n,1,pos);
85                 cout << pos << endl;
86                 update(pos, pos + d - 1, 0, 1, n, 1);
87             }
88         }
89         else{
90             cin >> x >> d;
91             update(x, x + d - 1, 1, 1, n, 1);
92         }
93     }return 0;
94 }