代码不规范,调到泪目
保留区间的左端点和右端点权值,以区间左端点为起点的最长递增序列长度 以区间右端点为终点的最长递增序列长度 区间的最大递增序列长度
#include<cstdio>
#include<iostream>
#define ll long long
using namespace std;
const int MAXN=1e5+10;
const int MAXM=1e6;
const int mod=1e9+7;
const int inf=0x3f3f3f3f;
struct Tree{
int l,r,len;
int lv,rv;
int lsum,rsum;
int sum;
}tree[MAXN<<2];
int a[MAXN];
void up(int x){
tree[x].lv=tree[x<<1].lv;
tree[x].rv=tree[x<<1|1].rv;
tree[x].lsum=tree[x<<1].lsum;
tree[x].rsum=tree[x<<1|1].rsum;
tree[x].sum=max(tree[x<<1].sum,tree[x<<1|1].sum);
if (tree[x<<1].rv<tree[x<<1|1].lv)
{
if (tree[x<<1].lsum==tree[x<<1].len)
tree[x].lsum+=tree[x<<1|1].lsum;//左半区间完全容纳最长递增序列 向右延伸
if (tree[x<<1|1].rsum==tree[x<<1|1].len)
tree[x].rsum+=tree[x<<1].rsum;
tree[x].sum=max(tree[x].sum,max(tree[x].lsum,tree[x].rsum));//更新
tree[x].sum=max(tree[x].sum,tree[x<<1].rsum+tree[x<<1|1].lsum);
}
//printf("tree[%d].lv=%d tree[%d].rv=%d tree[%d].lsum=%d tree[%d].rsum=%d\n",x,tree[x].lv,x,tree[x].rv,x,tree[x].lsum,x,tree[x].rsum);
}
/*
void up(int o){
tree[o].lv=tree[o<<1].lv;
tree[o].rv=tree[o<<1|1].rv;
tree[o].lsum=tree[o<<1].lsum;
tree[o].rsum=tree[o<<1|1].rsum;
tree[o].sum=max(tree[o<<1].sum,tree[o<<1|1].sum);
if(tree[o<<1].rv<tree[o<<1|1].lv){
if(tree[o<<1].lsum==tree[o<<1].len) //左半区间完全容纳最长递增序列 向右延伸
tree[o].lsum+=tree[o<<1|1].lsum;
if(tree[o<<1|1].rsum==tree[o<<1|1].len) //右半区间完全容纳最长递增序列 向左延伸
tree[o].rsum+=tree[o<<1].rsum;
tree[o].sum=max(tree[o].sum,max(tree[o].lsum,tree[o].rsum)); //更新
tree[o].sum=max(tree[o].sum,tree[o<<1].rsum+tree[o<<1|1].lsum);
}
printf("tree[%d].lv=%d tree[%d].rv=%d tree[%d].lsum=%d tree[%d].rsum=%d\n",o,tree[o].lv,o,tree[o].rv,o,tree[o].lsum,o,tree[o].rsum);
}
*/
void build(int l,int r,int x){
tree[x].l=l;tree[x].r=r;tree[x].len=r-l+1;
// printf("l=%d,r=%d,x=%d\n",l,r,x);
if(l==r){
int val;scanf("%d",&val);
tree[x].lv=tree[x].rv=val;
tree[x].lsum=tree[x].rsum=tree[x].sum=1;
return;
}
int mid=(tree[x].l+tree[x].r)>>1;
build(l,mid,x<<1);
build(mid+1,r,x<<1|1);
//printf("tree[x].sum=%d\n",tree[x].sum);
up(x);
}
void update(int x,int d,int v){
if (tree[x].l==tree[x].r){
tree[x].lv=tree[x].rv=v;
return;
}
int mid=(tree[x].l+tree[x].r)>>1;
if (d<=mid) update(x<<1,d,v);
else update(x<<1|1,d,v);
up(x);
}
int query(int l,int r,int x){
// printf("tree[%d].sum=%d\n",x,tree[x].sum);
if (l<=tree[x].l&&tree[x].r<=r)
return tree[x].sum;
int mid=(tree[x].l+tree[x].r)>>1;
if (r<=mid) return query(l,r,x<<1);
else if (l>mid) return query(l,r,x<<1|1);
else{
int a=query(l,mid,x<<1);
int b=query(mid+1,r,x<<1|1);
int ans=max(a,b);
if (tree[x<<1].rv<tree[x<<1|1].lv)
{
ans=max(ans,min(tree[x<<1].rsum,mid-l+1)+min(tree[x<<1|1].lsum,r-mid));
}
return ans;
}
}
/*int Query(int o,int le,int ri){
printf("tree[%d].sum=%d\n",o,tree[o].sum);
if(le<=tree[o].l&&tree[o].r<=ri) {
return tree[o].sum;
}
int mid=(tree[o].l+tree[o].r)>>1;
if(ri<=mid) return Query(o<<1,le,ri);
else if(le>mid) return Query(o<<1|1,le,ri);
else {
int a=Query(o<<1,le,mid);
int b=Query(o<<1|1,mid+1,ri);
int ans=max(a,b);
if(tree[o<<1].rv<tree[o<<1|1].lv) { // 不在区间里的话,会查询两个部分的最大值,
//但是其实这两个部分是连着的,所以有的这里的代码
ans=max(ans,min(tree[o<<1].rsum,mid-le+1)+min(tree[o<<1|1].lsum,ri-mid));
}
return ans;
}
}*/
int main(){
// fread();
// fwrite();
int T;scanf("%d",&T);
while(T--){
int n,q;
scanf("%d%d",&n,&q);
// printf("%d",n);
build(0,n-1,1);
char op[5];
while(q--){
int a,b;
scanf("%s%d%d",op,&a,&b);
if(op[0]=='U') update(1,a,b);
else
printf("%d\n",query(a,b,1));
}
}
return 0;
}