题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3308 线段树单点更新+区间合并，特殊的地方就是合并的时候考虑两个相邻的数是否符合条件，判断一下再决定是否合并
  view code
1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 #include <algorithm>
5 using namespace std;
6 #define lson l, m, rt<<1
7 #define rson m + 1, r, rt<<1|1
8 const int maxn = 111111;
9 int llci[maxn<<2], rlci[maxn<<2], mlci[maxn<<2];
10 int a[maxn];
11 void PushUp(int l, int r, int rt){
12 llci[rt] = llci[rt<<1];
13 rlci[rt] = rlci[rt<<1|1];
14 mlci[rt] = max(mlci[rt<<1], mlci[rt<<1|1]);
15 int m = (l + r) >> 1;
16 if (a[m] < a[m + 1]){
17 if (llci[rt] == m - l + 1) llci[rt] += llci[rt<<1|1];
18 if (rlci[rt] == r - m) rlci[rt] += rlci[rt<<1];
19 mlci[rt] = max(mlci[rt], llci[rt<<1|1] + rlci[rt<<1]);
20 }
21 }
22 void build(int l, int r, int rt){
23 if (l == r){
24 llci[rt] = rlci[rt] = mlci[rt] = 1;
25 return;
26 }
27 int m = (l + r) >> 1;
28 build(lson);
29 build(rson);
30 PushUp(l, r, rt);
31 }
32 void update(int x, int c, int l, int r, int rt){
33 if (l == r){
34 a[l] = c;
35 return;
36 }
37 int m = (l + r) >> 1;
38 if (x <= m) update(x, c, lson);
39 else update(x, c, rson);
40 PushUp(l, r, rt);
41 }
42 int query(int ll, int rr, int l, int r, int rt){
43 if (ll == l && rr == r) return mlci[rt];
44 int m = (l + r) >> 1;
45 if (rr <= m) return query(ll, rr, lson);
46 else if (ll > m) return query(ll, rr, rson);
47 else{
48 int x = query(ll, m, lson);
49 int y = query(m + 1, rr, rson);
50 int z = 0;
51 if (a[m] < a[m + 1]){
52 z += min(llci[rt<<1|1], rr - m);
53 z += min(rlci[rt<<1], m - ll + 1);
54 }
55 return max(x, max(y, z));
56 }
57 }
58 int main(){
59 int t;
60 scanf("%d", &t);
61 while (t--){
62 int n, m;
63 scanf("%d%d", &n, &m);
64 for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
65 build(1, n, 1);
66 char op[2]; int x, y;
67 while (m--){
68 scanf("%s%d%d", op, &x, &y);
69 x += 1;
70 if (op[0] == 'U') update(x, y, 1, n, 1);
71 else{
72 y += 1;
73 int ans = query(x, y, 1, n, 1);
74 printf("%d\n", ans);
75 }
76 }
77 }
78 return 0;
79
|