题意

q种操作，查询区间内最长连续上升子序列的长度，或者修改某个点的值

题解

线段树维护：区间内最长连续上升子序列的长度sub、区间内以左端点为起点的最长连续上升子序列的长度lsub、区间内以右端点为终点的最长连续上升子序列的长度rsub、区间左端点的值l和右端点的值r。

1 #define IO std::ios::sync_with_stdio(0); 2 #include 
     
       3 #define iter ::iterator 4 using namespace  std; 5 typedef long long ll; 6 typedef pair
      
       P; 7 #define pb push_back 8 #define se second 9 #define fi first10 #define rs o*2+111 #define ls o*212 const ll inf=0x7fffffff;13 const int N=1e5+5;14 struct node{15     int sub;16     int lsub,rsub;17     int l,r;18 }a[N*4];19 void pu(int o,int len){20     a[o].l=a[ls].l;21     a[o].r=a[rs].r;22     a[o].sub=max(a[ls].sub,a[rs].sub);23     if(a[rs].l>a[ls].r){24         a[o].sub=max(a[o].sub,a[ls].rsub+a[rs].lsub);25     }26     a[o].lsub=a[ls].lsub;27     if(a[ls].lsub==len-len/2&&a[rs].l>a[ls].r){28         a[o].lsub+=a[rs].lsub;29     }30     a[o].rsub=a[rs].rsub;31     if(a[o].rsub==len/2&&a[rs].l>a[ls].r){32         a[o].rsub+=a[ls].rsub;33     }34 }35 void build(int o,int l,int r){36     if(l==r){37         int x;38         scanf("%d",&x);39         a[o].l=a[o].r=x;40         a[o].sub=a[o].lsub=a[o].rsub=1;41         return;42     }43     int m=(l+r)/2;44     build(ls,l,m);45     build(rs,m+1,r);46     pu(o,r-l+1);47 }48 void up(int o,int l,int r,int p,int v){49     if(l==r&&l==p){50         a[o].l=a[o].r=v;51         return;52     }53     int m=(l+r)/2;54     if(p<=m)up(ls,l,m,p,v);55     else up(rs,m+1,r,p,v);56     pu(o,r-l+1);57 }58 int query(int o,int l,int r,int ql,int qr){59     if(l>=ql&&r<=qr){60         return a[o].sub;61     }62     int m=(l+r)/2;63     int res=0;64     if(ql<=m)res=max(res,query(ls,l,m,ql,qr));65     if(qr>m)res=max(res,query(rs,m+1,r,ql,qr));66     if(ql<=m&&qr>m&&a[ls].r