线段树，题目感觉比较难，看别人思路做的。还得继续练这个专题。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std; #define MAXN 100005
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1 int str[MAXN<<], lstr[MAXN<<], rstr[MAXN<<];
int nums[MAXN]; inline int mymax(int a, int b) {
return (a>b) ? a:b;
} inline int mymin(int a, int b) {
return (a<b) ? a:b;
} void PushUP(int l, int r, int rt) {
int mid; str[rt] = mymax(str[rt<<], str[rt<<|]);
lstr[rt] = lstr[rt<<];
rstr[rt] = rstr[rt<<|]; mid = (l+r)>>;
if (nums[mid] < nums[mid+]) {
if (lstr[rt] == mid-l+)
lstr[rt] += lstr[rt<<|];
if (rstr[rt] == r-mid)
rstr[rt] += rstr[rt<<];
str[rt] = mymax(str[rt], lstr[rt<<|]+rstr[rt<<]);
}
} void build(int l, int r, int rt) {
int mid;
if (l == r) {
str[rt] = lstr[rt] = rstr[rt] = ;
return ;
}
mid = (l+r)>>;
build(lson);
build(rson);
PushUP(l, r, rt);
} void update(int x, int c, int l, int r, int rt) {
int mid;
if (l == r) {
nums[x] = c;
return ;
}
mid = (l+r)>>;
if (x <= mid)
update(x, c, lson);
else
update(x, c, rson);
PushUP(l, r, rt);
} int query(int ll, int rr, int l, int r, int rt) {
int mid, ret = ;
if (ll<=l && rr>=r)
return str[rt]; mid = (l+r)>>;
if (ll <= mid)
ret = mymax(ret, query(ll,rr,lson));
if (rr > mid)
ret = mymax(ret, query(ll,rr,rson)); if (ll<=mid && mid<rr && nums[mid]<nums[mid+]) {
ret = mymax(ret, mymin(mid-ll+,rstr[rt<<])+mymin(lstr[rt<<|],rr-mid));
} return ret;
} void output(int beg, int end) {
int i;
for (i=beg; i<end; ++i)
printf("\t%d: l=%d,s=%d,w=%d\n", i, lstr[i], rstr[i], str[i]);
} int main() {
int case_n, n, m;
int i, x, y;
char cmd[]; scanf("%d", &case_n); while (case_n--) {
scanf("%d %d", &n, &m);
for (i=; i<n; ++i)
scanf("%d", &nums[i]);
build(, n-, );
while (m--) {
scanf("%s %d %d", cmd, &x, &y);
if (cmd[] == 'Q') {
printf("%d\n", query(x,y,,n-,));
} else {
update(x, y, , n-, );
}
//output(1, 18);
}
} return ;
}