hdu 3308 LCIS

http://acm.hdu.edu.cn/showproblem.php?pid=3308

　　又是一题区间合并的题，今晚就这题就debug到我晕了。。。。。

　　同样是之前poj那题的错误，就是区间合并的部分思路混乱了一下。

　　题目很简洁，就是要求区间的最大上升子串，同时要有动态的单点更新！线段树功能【单点更新，查询区间】。

　　题目告诉我，我应该找多点这样的题来做，从而防止这样的思维混乱再次发生，因为这明显就是应该1y的水题！- -

View Code

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <cstdlib>
  4 #include <algorithm>
  5 #include <vector>
  6 #include <cassert>
  7 
  8 using namespace std;
  9 
 10 #define lson l, m, rt << 1
 11 #define rson m + 1, r, rt << 1 | 1
 12 const int maxn = 100005;
 13 
 14 int lval[maxn << 2], rval[maxn << 2], llen[maxn << 2], rlen[maxn << 2], mx[maxn << 2];
 15 struct Node{
 16     int lval, rval;
 17     int llen, rlen;
 18     int mx;
 19     Node() {}
 20     Node(int lv, int rv, int ll, int rl, int m):
 21         lval(lv), rval(rv), llen(ll), rlen(rl), mx(m) {}
 22 };
 23 
 24 void up(int rt, int len){ // 关键位置，容易发生错漏
 25     int l = rt << 1;
 26     int r = rt << 1 | 1;
 27     int m1 = len >> 1, m2 = len - m1;
 28 
 29     mx[rt] = max(mx[l], mx[r]);
 30     llen[rt] = llen[l];
 31     rlen[rt] = rlen[r];
 32     if (rval[l] < lval[r]){
 33         mx[rt] = max(mx[rt], rlen[l] + llen[r]);
 34         if (llen[l] == m2) llen[rt] = llen[l] + llen[r];
 35         if (rlen[r] == m1) rlen[rt] = rlen[r] + rlen[l];
 36     }
 37     lval[rt] = lval[l];
 38     rval[rt] = rval[r];
 39 }
 40 
 41 void build(int l, int r, int rt){
 42     if (l == r){
 43         int tmp;
 44 
 45         scanf("%d", &tmp);
 46         lval[rt] = rval[rt] = tmp;
 47         mx[rt] = llen[rt] = rlen[rt] = 1;
 48 
 49         return ;
 50     }
 51     int m = (l + r) >> 1;
 52 
 53     build(lson);
 54     build(rson);
 55     up(rt, r - l + 1);
 56 //printf("%d %d : len %d %d val %d %d mx %d\n", l, r, llen[rt], rlen[rt], lval[rt], rval[rt], mx[rt]);
 57 }
 58 
 59 void modify(int pos, int key, int l, int r, int rt){
 60     if (l == r){
 61 //assert(l == pos);
 62         lval[rt] = rval[rt] = key;
 63 
 64         return ;
 65     }
 66     int m = (l + r) >> 1;
 67 
 68     if (pos <= m) modify(pos, key, lson);
 69     else modify(pos, key, rson);
 70     up(rt, r - l + 1);
 71 }
 72 
 73 Node query(int L, int R, int l, int r, int rt){
 74     Node ret;
 75     if (L <= l && r <= R){
 76         ret = Node(lval[rt], rval[rt], llen[rt], rlen[rt], mx[rt]);
 77 
 78         return ret;
 79     }
 80     int m = (l + r) >> 1;
 81     Node tmp;
 82 // 下面的也是关键位置，合并绝对不能水
 83     if (L <= m){
 84         int m1 = min(m - L + 1, m - l + 1);
 85         int m2 = min(R - m, r - m);
 86 
 87         ret = query(L, R, lson);
 88 //printf("%d %d : mx %d len %d %d val %d %d\n", l, m, ret.mx, ret.llen, ret.rlen, ret.lval, ret.rval);
 89         if (m < R){
 90             tmp = query(L, R, rson);
 91 //printf("%d %d : mx %d len %d %d val %d %d\n", m + 1, r, tmp.mx, tmp.llen, tmp.rlen, tmp.lval, tmp.rval);
 92             ret.mx = max(ret.mx, tmp.mx);
 93             if (ret.rval < tmp.lval){
 94                 ret.mx = max(ret.mx, ret.rlen + tmp.llen);
 95             }
 96             if (ret.llen == m1 && ret.rval < tmp.lval) ret.llen += tmp.llen;
 97             if (tmp.rlen == m2 && ret.rval < tmp.lval) ret.rlen += tmp.rlen;
 98             else ret.rlen = tmp.rlen;
 99             ret.rval = tmp.rval;
100         }
101         return ret;
102     }
103     if (m < R) ret = query(L, R, rson);
104 //printf("%d %d : mx %d len %d %d val %d %d\n", m + 1, r, ret.mx, ret.llen, ret.rlen, ret.lval, ret.rval);
105 
106     return ret;
107 }
108 
109 void deal(int n, int m){
110     char buf[3];
111 
112     build(0, n - 1, 1);
113     while (m--){
114         int l, r;
115 
116         scanf("%s%d%d", buf, &l, &r);
117 //assert(buf[0] == 'Q' || buf[0] == 'U');
118         if (buf[0] == 'Q'){
119             printf("%d\n", query(l, r, 0, n - 1, 1).mx);
120         }
121         else if (buf[0] == 'U'){
122             modify(l, r, 0, n - 1, 1);
123         }
124     }
125 }
126 
127 int main(){
128     int n, m;
129     int T;
130 
131 //freopen("in", "r", stdin);
132     scanf("%d", &T);
133     while (T-- && ~scanf("%d%d", &n, &m)){
134         deal(n, m);
135     }
136 
137     return 0;
138 }

——written by Lyon