题目大意：给n个数，两种操作1：U a b 更新第a个为b （从0开始）
2： Q a ,b 查询 a，b之间LCIS（最长连续递增子序列）的长度。
Sample Input
1
10 10
7 7 3 3 5 9 9 8 1 8
Q 6 6
U 3 4
Q 0 1
Q 0 5
Q 4 7
Q 3 5
Q 0 2
Q 4 6
U 6 10
Q 0 9
Sample Output
1
1
4
2
3
1
2
5
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <iostream>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define maxn 100005
using namespace std; int mlen[maxn<<],lmlen[maxn<<],rmlen[maxn<<];
int num[maxn]; void pushup(int rt,int l,int r)
{
lmlen[rt]=lmlen[rt<<];
rmlen[rt]=rmlen[rt<<|];
mlen[rt]=max(mlen[rt<<],mlen[rt<<|]);
int mid=(l+r)>>;
int m=(r-l)+;
if(num[mid]<num[mid+]) //左区间的右值小于右区间的左值可以合并
{
if(lmlen[rt]==m-(m>>)) lmlen[rt]+=lmlen[rt<<|];
if(rmlen[rt]==(m>>)) rmlen[rt]+=rmlen[rt<<];
mlen[rt]=max(mlen[rt],lmlen[rt<<|]+rmlen[rt<<]);
}
}
void build(int l,int r,int rt)
{
if(l==r)
{
mlen[rt]=lmlen[rt]=rmlen[rt]=;
return ;
}
int m=(l+r)>>;
build(lson);
build(rson);
pushup(rt,l,r);
}
void update(int a,int l,int r,int rt)
{
if(l==r)
{
return;
}
int m=(l+r)>>;
if(a<=m) update(a,lson);
else update(a,rson);
pushup(rt,l,r);
} int query(int L,int R,int l,int r,int rt)
{
//printf("%d %d %d %d %d\n",L,R,l,r,rt);
if(L<=l&&r<=R)
{
return mlen[rt];
}
int m=(l+r)>>;
if(R<=m) return query(L,R,lson); //与一般不同，不能是子集，只能全部属于才能直接查询子区间 返回子区间的mlen
if(L>m) return query(L,R,rson); //否则是确认儿子区间是否能合并，并在三者之间取最大值 int ta,tb;
ta=query(L,R,lson);
tb=query(L,R,rson);
int ans;
ans=max(ta,tb);
if(num[m]<num[m+]) //同上
{
int temp;
temp=min(rmlen[rt<<],m-L+)+min(lmlen[rt<<|],R-m);
ans=max(temp,ans);
}
return ans;
} int main()
{
int T,n,m;
int i,j;
char f[];
int a,b;
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
#endif
scanf("%d",&T);
for(i=;i<T;i++)
{
scanf("%d %d",&n,&m);
for(j=;j<=n;j++)
scanf("%d",&num[j]);
build(,n,);
while(m--)
{
scanf("%s",&f);
if(f[]=='U')
{
scanf("%d %d",&a,&b);
a++;
num[a]=b;
update(a,,n,);
}
else
{
scanf("%d %d",&a,&b);
a++,b++;
printf("%d\n",query(a,b,,n,));
}
}
}
return ;
}