poj 1823 Hotel

　　这是一道线段树的题，很久以前就听说它很经典！这是【成段更新，全段询问】的线段树。

　　题目要求的是更新指定区间，然后询问全部区间中连续区间的最大值。这题的时限比较紧，最好是用G++来做，C++我的代码超时了。。。。囧！

View Code

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 #include <cassert>
  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 = 16001;
 12 struct Hotel {
 13     int mx;
 14     int l, r;
 15 
 16     Hotel(int _set = 0): mx(_set), l(_set), r(_set) {}
 17 };
 18 Hotel seg[maxn << 2];
 19 int late[maxn << 2];
 20 
 21 void scan(int &a){
 22     char ch;
 23 
 24     while ((ch = getchar()) > '9' || ch < '0');
 25     a = ch - '0';
 26     while ((ch = getchar()) >= '0' && ch <= '9'){
 27         a = a * 10 + ch - '0';
 28     }
 29 }
 30 
 31 void down(int rt, int len) {
 32     if (~late[rt]) {
 33         int l = rt << 1;
 34         int r = rt << 1 | 1;
 35         int m = len >> 1;
 36 
 37         late[l] = late[r] = late[rt];
 38         seg[l] = Hotel(late[rt] * (len - m));
 39         seg[r] = Hotel(late[rt] * m);
 40         late[rt] = -1;
 41     }
 42 }
 43 
 44 Hotel up(Hotel left, Hotel right, int lLen, int rLen) {
 45     Hotel ret;
 46 
 47     ret.mx = max(left.mx, right.mx);
 48     ret.mx = max(ret.mx, left.r + right.l);
 49     ret.l = left.l;
 50     ret.r = right.r;
 51     if (left.l == lLen) ret.l += right.l;
 52     if (right.r == rLen) ret.r += left.r;
 53 
 54     return ret;
 55 }
 56 
 57 void build(int l, int r, int rt) {
 58     late[rt] = -1;
 59     if (l == r) {
 60         seg[rt] = Hotel(1);
 61 
 62         return ;
 63     }
 64     int m = (l + r) >> 1;
 65 
 66     build(lson);
 67     build(rson);
 68     seg[rt] = up(seg[rt << 1], seg[rt << 1 | 1], m + 1 - l, r - m);
 69 //    printf("@@@%d %d : %d %d %d\n", l, r, seg[rt].l, seg[rt].r, seg[rt].mx);
 70 }
 71 
 72 void update(int L, int R, int op, int l, int r, int rt) {
 73     if (L <= l && r <= R) {
 74         seg[rt] = Hotel(op * (r - l + 1));
 75         late[rt] = op;
 76 //        printf("!!!%d %d : %d %d %d\n", l, r, seg[rt].l, seg[rt].r, seg[rt].mx);
 77 
 78         return ;
 79     }
 80     int m = (l + r) >> 1;
 81 
 82     down(rt, r - l + 1);
 83     if (L <= m) update(L, R, op, lson);
 84     if (m < R) update(L, R, op, rson);
 85     seg[rt] = up(seg[rt << 1], seg[rt << 1 | 1], m + 1 - l, r - m);
 86 //    printf("!!!%d %d : %d %d %d\n", l, r, seg[rt].l, seg[rt].r, seg[rt].mx);
 87 }
 88 
 89 void deal(int len, int n) {
 90     int op, x, y;
 91 
 92     build(1, len, 1);
 93     while (n--) {
 94         scan(op);
 95         switch (op) {
 96         case 1: {
 97             //scanf("%d%d", &x, &y);
 98             scan(x);
 99             scan(y);
100             update(x, x + y - 1, 0, 1, len, 1);
101         }
102         break;
103         case 2: {
104             //scanf("%d%d", &x, &y);
105             scan(x);
106             scan(y);
107             update(x, x + y - 1, 1, 1, len, 1);
108         }
109         break;
110         case 3: {
111             printf("%d\n", seg[1].mx);
112         }
113         break;
114         default:
115             return ;
116         }
117     }
118 }
119 
120 int main() {
121     int n, p;
122 
123     while (~scanf("%d%d", &n, &p)) {
124         deal(n, p);
125     }
126 
127     return 0;
128 }

——written by Lyon