Problem Description
Given n integers.
You have two operations:
U A B: replace the Ath number by B. (index counting from 0)
Q A B: output the length of the longest consecutive increasing subsequence (LCIS) in [a, b].
You have two operations:
U A B: replace the Ath number by B. (index counting from 0)
Q A B: output the length of the longest consecutive increasing subsequence (LCIS) in [a, b].
Input
T in the first line, indicating the case number.
Each case starts with two integers n , m(0<n,m<=10
).
The next line has n integers(0<=val<=10
).
The next m lines each has an operation:
U A B(0<=A,n , 0<=B=10
)
OR
Q A B(0<=A<=B< n).
Each case starts with two integers n , m(0<n,m<=10
).
The next line has n integers(0<=val<=10
).
The next m lines each has an operation:
U A B(0<=A,n , 0<=B=10
)
OR
Q A B(0<=A<=B< n).
Output
For each Q, output the answer.
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
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
1
4
2
3
1
2
5
题意：输入Q，则查寻范围[A,B]内的最长升序，输入U，则更新点A的值变成B。
解题：记录第个节点的最左端的升序长度，最右端的升序的长度和在这个范围内的最长升序。而父节点的则是由左右节点产生。
1. 左儿子最右边的值 < 右儿子最左边的值
lMax = (左儿子的lMax == 左儿子的len) ? 左儿子的len + 右儿子的lMax : 左儿子的lMax;
rMax = (右儿子的rMax == 右儿子的len) ? 右儿子的len + 左儿子的rMax : 右儿子的rMax;
Max = MAX(左儿子的rMax + 右儿子的lMax, 左儿子的Max, 右儿子的Max, lMax, rMax);
2. 左儿子最右边的值 >= 右儿子最左边的值
lMax = 左儿子的lMax;
rMax = 右儿子的rMax;
Max = MAX(左儿子的Max, 右儿子的Max);注意：在查寻时，当跨越左右子树时则一这要注意这个，当 左节点的最右边的值< 右节点的最左边的值时，那么有可能最长升序在这时最大，并且不能超过这个范围。
#include<stdio.h>
#define N 500010
struct node
{
int Llcis,Rlcis,lcis;//最左连续升序长度，最右连续升序长度，这个范围的最长连续升序长度
}tree[8*N];
int num[N+5];
int max(int a,int b){ return a>b?a:b;}
void chang_tree(int l,int r,int k)//根据第K个节点的左右节点,计算第K个节点的最左，最右和最长 的升序长度
{
int m=(l+r)/2;
node ltree=tree[k*2],rtree=tree[k*2+1];
if(num[m]>=num[m+1])//当左节点的最右边的值不小右节点的最左边的值时
{
tree[k].Llcis=ltree.Llcis;
tree[k].Rlcis=rtree.Rlcis;
tree[k].lcis=max(ltree.lcis,rtree.lcis);
}
else
{
if(m-l+1==ltree.Llcis) tree[k].Llcis=ltree.Llcis+rtree.Llcis;
else tree[k].Llcis=ltree.Llcis;
if(r-m==rtree.Rlcis) tree[k].Rlcis=rtree.Rlcis+ltree.Rlcis;
else tree[k].Rlcis=rtree.Rlcis;
tree[k].lcis=max(ltree.lcis,ltree.Rlcis+rtree.Llcis);
tree[k].lcis=max(tree[k].lcis,rtree.lcis);
tree[k].lcis=max(tree[k].lcis,tree[k].Llcis);
tree[k].lcis=max(tree[k].lcis,tree[k].Rlcis);
}
}
void build(int l,int r,int k)
{
int m=(l+r)/2;
if(l==r){
tree[k].Llcis=1;
tree[k].lcis=1;
tree[k].Rlcis=1;
return ;
}
build(l,m,k*2);
build(m+1,r,k*2+1);
chang_tree(l,r,k);
}
void updata(int l,int r,int k,int Q,int ans)
{
int m=(l+r)/2;
if(l==Q&&Q==r)
{num[Q]=ans; return ;}
if(Q<=m) updata(l,m,k*2,Q,ans);
if(Q>m) updata(m+1,r,k*2+1,Q,ans);
chang_tree(l,r,k);
}
int maxlen;
void find(int l,int r,int k,int L,int R)
{
int m=(l+r)/2;
if(L<=l&&r<=R){
maxlen=max(tree[k].lcis,maxlen);
return ;
}
if(R<=m) find(l,m,k*2,L,R);
else if(L>m) find(m+1,r,k*2+1,L,R);
else{
find(l,m,k*2,L,R);
find(m+1,r,k*2+1,L,R);
//-----当查寻夸越左右子树时,左子树的最右端点的值小于右子树的最左端点的值------
if(num[m]<num[m+1])
if(L<=m-tree[2*k].Rlcis+1&&m+tree[k*2+1].Llcis<=R)//注意这个条件
maxlen=max(tree[k*2].Rlcis+tree[k*2+1].Llcis,maxlen);
else if(L<=m-tree[2*k].Rlcis+1&&m+tree[k*2+1].Llcis>R)//注意这个条件
maxlen=max(tree[k*2].Rlcis+R-m,maxlen);
else if(L>m-tree[2*k].Rlcis+1&&m+tree[k*2+1].Llcis<=R)//注意这个条件
maxlen=max(m-L+1+tree[k*2+1].Llcis,maxlen);
else maxlen=R-L+1;//最长的升序长度
}
}
int main()
{
int t,n,m,QL,QR;
char c[2];
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&num[i]);
build(1,n,1);
while(m--)
{
scanf("%s%d%d",c,&QL,&QR);
if(c[0]=='U') updata(1,n,1,QL+1,QR);
if(c[0]=='Q')
{
maxlen=0; find(1,n,1,QL+1,QR+1);
printf("%d\n",maxlen);
}
}
}
}