维护一个区间的包含最左的元素的LCIS，包含最右元素的LCIS，以及整个区间的LCIS，
然后pushup的时候就更新这三个值就行了。注意要考虑左右儿子可以“接”起来的情况等等
查询的时候要注意，也要考虑左右可以“接”起来时候，不过还要注意，有可能左右儿子边界的已经“越界了”，就是超过了查询范围，还要取个min，这道题坑就坑在这儿
#include<bits/stdc++.h> #define N 100005 using namespace std; int n,m,val[N]; struct node { int l,r,lmax,rmax,maxv; }tree[4*N]; inline void pushup(int now) { int m=(tree[now].l+tree[now].r)>>1; if(val[m]<val[m+1]) { tree[now].lmax=(tree[2*now].lmax==tree[2*now].r-tree[2*now].l+1)?tree[2*now].lmax+tree[2*now+1].lmax:tree[2*now].lmax; tree[now].rmax=(tree[2*now+1].rmax==tree[2*now+1].r-tree[2*now+1].l+1)?tree[2*now+1].rmax+tree[2*now].rmax:tree[2*now+1].rmax; int e1=tree[2*now].rmax+tree[2*now+1].lmax; int e2=tree[2*now].maxv,e3=tree[2*now+1].maxv; int e4=tree[now].lmax,e5=tree[now].rmax; tree[now].maxv=max(max(max(e1,e2),max(e3,e4)),e5); } else { tree[now].lmax=tree[2*now].lmax; tree[now].rmax=tree[2*now+1].rmax; tree[now].maxv=max(tree[2*now].maxv,tree[2*now+1].maxv); } } void build(int now,int l,int r) { tree[now].l=l,tree[now].r=r; if(l==r) { tree[now].lmax=1; tree[now].rmax=1; tree[now].maxv=1; return; } int m=(l+r)>>1; build(2*now,l,m); build(2*now+1,m+1,r); pushup(now); } inline void update(int now,int pos) { if(tree[now].l==tree[now].r&&tree[now].l==pos) { return; } int m=(tree[now].l+tree[now].r)>>1; if(pos<=m) update(2*now,pos); else update(2*now+1,pos); pushup(now); } int ret=0; void query(int now,int l,int r) { if(l<=tree[now].l&&tree[now].r<=r) { ret=max(ret,tree[now].maxv); return; } int m=(tree[now].l+tree[now].r)>>1; if(l<=m) query(2*now,l,r); if(r>m) query(2*now+1,l,r); if(val[m]<val[m+1]) { int temp; temp=min(tree[2*now].rmax,m-l+1)+min(tree[2*now+1].lmax,r-m); ret=max(ret,temp); } } int main() { int T; cin>>T; while(T--) { cin>>n>>m; for(int i=1;i<=n;i++) cin>>val[i]; build(1,1,n); char ch; int x,y; while(m--) { cin>>ch>>x>>y; if(ch=='U') //update { x++; val[x]=y; update(1,x); } else { x++,y++; ret=0; query(1,x,y); cout<<ret<<endl; } } } }