HDU 3308 LCIS（线段树）

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 const int MAXN = 100010 << 2;
 8 
 9 int lmax[MAXN], rmax[MAXN], mmax[MAXN];
10 int a[MAXN], n, m, T;
11 
12 void update(int x, int l, int r, int pos, int val) {
13     if(pos <= l && r <= pos) {
14         a[pos] = val;
15     } else {
16         int ll = x << 1, rr = ll | 1, mid = (l + r) >> 1;
17         if(pos <= mid) update(ll, l, mid, pos, val);
18         if(mid < pos) update(rr, mid + 1, r, pos, val);
19         if(a[mid] < a[mid + 1]) {
20             lmax[x] = lmax[ll] + (lmax[ll] == mid - l + 1) * lmax[rr];
21             rmax[x] = rmax[rr] + (rmax[rr] == r - mid) * rmax[ll];
22             mmax[x] = max(rmax[ll] + lmax[rr], max(mmax[ll], mmax[rr]));
23         } else {
24             lmax[x] = lmax[ll];
25             rmax[x] = rmax[rr];
26             mmax[x] = max(mmax[ll], mmax[rr]);
27         }
28     }
29 }
30 
31 int query(int x, int l, int r, int aa, int bb) {
32     if(aa <= l && r <= bb) {
33         return mmax[x];
34     } else {
35         int ll = x << 1, rr = ll | 1, mid = (l + r) >> 1;
36         int ans = 0;
37         if(aa <= mid) ans = max(ans, query(ll, l, mid, aa, bb));
38         if(mid < bb) ans = max(ans, query(rr, mid + 1, r, aa, bb));
39         if(a[mid] < a[mid + 1]) ans = max(ans, min(rmax[ll], mid - aa + 1) + min(lmax[rr], bb - mid));
40         return ans;
41     }
42 }
43 
44 void build(int x, int l, int r) {
45     if(l == r) {
46         lmax[x] = rmax[x] = mmax[x] = 1;
47     } else {
48         int ll = x << 1, rr = ll | 1, mid = (l + r) >> 1;
49         build(ll, l, mid);
50         build(rr, mid + 1, r);
51         if(a[mid] < a[mid + 1]) {
52             lmax[x] = lmax[ll] + (lmax[ll] == mid - l + 1) * lmax[rr];
53             rmax[x] = rmax[rr] + (rmax[rr] == r - mid) * rmax[ll];
54             mmax[x] = max(rmax[ll] + lmax[rr], max(mmax[ll], mmax[rr]));
55         } else {
56             lmax[x] = lmax[ll];
57             rmax[x] = rmax[rr];
58             mmax[x] = max(mmax[ll], mmax[rr]);
59         }
60     }
61 }
62 
63 int main() {
64     scanf("%d", &T);
65     while(T--) {
66         scanf("%d%d", &n, &m);
67         for(int i = 0; i < n; ++i) scanf("%d", &a[i]);
68         build(1, 0, n - 1);
69         while(m--) {
70             char c;
71             int a, b;
72             scanf(" %c%d%d", &c, &a, &b);
73             if(c == ‘Q‘) printf("%d\n", query(1, 0, n - 1, a, b));
74             else update(1, 0, n - 1, a, b);
75         }
76     }
77 }