poj 3667 Hotel

　　又是一道线段树的题，这次的操作是【区间更新，查询最大连续区间】。这题是之前一题"内存管理"的模拟题的简化版，在插入区间前先查找满足要求的位置，然后就直接整段覆盖，删除也就是简单的删除区间。注意细节就好了！

　　刚开始的时候打算查找和覆盖打在一起，后来发现这样的操作十分困难，所以还是将查找和覆盖分离了。所以插入区间和删除区间也变成两部分了。

代码如下：

View Code

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <cstdlib>
  4 #include <algorithm>
  5 
  6 using namespace std;
  7 
  8 #define lson l, m, rt << 1
  9 #define rson m + 1, r, rt << 1 | 1
 10 
 11 const int maxn = 50005;
 12 
 13 struct Hotel {
 14     int mx, len;
 15     int l, r;
 16 
 17     Hotel(int _len = 0, int _set = 0) {
 18         mx = l = r = _set;
 19         len = _len;
 20     }
 21 } room[maxn << 2];
 22 int late[maxn << 2];
 23 
 24 Hotel up(Hotel left, Hotel right) {
 25     Hotel ret;
 26 
 27     ret.len = left.len + right.len;
 28     ret.mx = max(left.mx, right.mx);
 29     ret.mx = max(ret.mx, left.r + right.l);
 30     ret.l = left.l;
 31     ret.r = right.r;
 32     if (left.l == left.len) ret.l += right.l;
 33     if (right.r == right.len) ret.r += left.r;
 34 
 35     return ret;
 36 }
 37 
 38 void down(int rt) {
 39     if (~late[rt]) {
 40         int l = rt << 1;
 41         int r = rt << 1 | 1;
 42 
 43         late[l] = late[r] = late[rt];
 44         room[l] = Hotel(room[l].len, late[rt] * room[l].len);
 45         room[r] = Hotel(room[r].len, late[rt] * room[r].len);
 46         late[rt] = -1;
 47     }
 48 }
 49 
 50 void build(int l, int r, int rt) {
 51     late[rt] = -1;
 52     if (l == r) {
 53         room[rt] = Hotel(1, 1);
 54 //printf("%d %d : %d %d %d %d\n", l, r, room[rt].mx, room[rt].len, room[rt].l, room[rt].r);
 55 
 56         return ;
 57     }
 58     int m = (l + r) >> 1;
 59 
 60     build(lson);
 61     build(rson);
 62     room[rt] = up(room[rt << 1], room[rt << 1 | 1]);
 63 //printf("%d %d : %d %d %d %d\n", l, r, room[rt].mx, room[rt].len, room[rt].l, room[rt].r);
 64 }
 65 
 66 int find(int len, int l, int r, int rt){
 67     if (room[rt].mx < len) return 0;
 68     if (room[rt].len == room[rt].mx) return l;
 69 
 70     int m = (l + r) >> 1;
 71 
 72     if (room[rt << 1].mx >= len) return find(len, lson);
 73     if (room[rt << 1].r + room[rt << 1 | 1].l >= len) return m - room[rt << 1].r + 1;
 74     return find(len, rson);
 75 }
 76 
 77 void add(int L, int R, int l, int r, int rt) {
 78     if (L <= l && r <= R){
 79         late[rt] = 0;
 80         room[rt] = Hotel(room[rt].len);
 81 //printf("%d %d : %d %d %d %d\n", l, r, room[rt].mx, room[rt].len, room[rt].l, room[rt].r);
 82 
 83         return ;
 84     }
 85     int m = (l + r) >> 1;
 86 
 87     down(rt);
 88     if (L <= m) add(L, R, lson);
 89     if (m < R) add(L, R, rson);
 90     room[rt] = up(room[rt << 1], room[rt << 1 | 1]);
 91 //printf("%d %d : %d %d %d %d\n", l, r, room[rt].mx, room[rt].len, room[rt].l, room[rt].r);
 92 }
 93 
 94 void sub(int L, int R, int l, int r, int rt) {
 95     if (L <= l && r <= R) {
 96         late[rt] = 1;
 97         room[rt] = Hotel(room[rt].len, room[rt].len);
 98 //printf("%d %d : %d %d %d %d\n", l, r, room[rt].mx, room[rt].len, room[rt].l, room[rt].r);
 99 
100         return ;
101     }
102     int m = (l + r) >> 1;
103 
104     down(rt);
105     if (L <= m) sub(L, R, lson);
106     if (m < R) sub(L, R, rson);
107     room[rt] = up(room[rt << 1], room[rt << 1 | 1]);
108 //printf("%d %d : %d %d %d %d\n", l, r, room[rt].mx, room[rt].len, room[rt].l, room[rt].r);
109 }
110 
111 void deal(int n, int m) {
112     build(1, n, 1);
113     while (m--) {
114         int op;
115         int x, y;
116 
117         scanf("%d", &op);
118         if (op == 1) {
119             scanf("%d", &x);
120 
121             int pos = find(x, 1, n, 1);
122 
123             printf("%d\n", pos);
124             if (pos) add(pos, pos + x - 1, 1, n, 1);
125         } else {
126             scanf("%d%d", &x, &y);
127             sub(x, x + y - 1, 1, n, 1);
128         }
129     }
130 }
131 
132 int main() {
133     int n, m;
134 
135 //freopen("in", "r", stdin);
136     while (~scanf("%d%d", &n, &m)) {
137         deal(n, m);
138     }
139 
140     return 0;
141 }

——written by Lyon