题目链接

【题意】

给定长度为 $n$ 的序列，有2种操作

$UAB$ 将下标为 $A$ 的元素修改为 $B$

$QAB$ 查询区间 $[A,B]$ 的最长连续上升子序列长度（LCIS，不是LIS，必须连续）

下标从0开始 (n,q&lt;=105，元素值&lt;=105)(n,q&lt;=10^5，元素值&lt;=10^5)(n,q<=105，元素值<=105)

【思路】

线段树区间合并，区间维护5个属性，$sum$ 为最长连续上升子序列长度，$sumL$ 为以左端点为起点的最长连续上升子序列长度，$sumR$ 为以右端点为终点的最长连续上升子序列长度，$Lv$ 为左端点值，$Rv$ 为右端点值

#include
    
     #define node tree[id]#define lson tree[id<<1]#define rson tree[id<<1|1]using namespace std;const int maxn=100005;struct Node{	int sum,sumL,sumR;	int Lv,Rv;	Node(int s=0,int sL=0,int sR=0,int L=0,int R=0):sum(s),sumL(sL),sumR(sR),Lv(L),Rv(R){}};struct Tree{	int left,right;	int sum,sumL,sumR;	int Lv,Rv;}tree[maxn<<2];int n,q;int a[maxn];void pushup(int id){	node.Lv=lson.Lv;	node.Rv=rson.Rv;	node.sumL=lson.sumL;	node.sumR=rson.sumR;	node.sum=max(lson.sum,rson.sum);	if(lson.Rv
     
      >1;	build(id<<1,le,mid);	build(id<<1|1,mid+1,ri);	pushup(id);}Node query(int id,int le,int ri){	if(node.left==le && node.right==ri){		return Node(node.sum,node.sumL,node.sumR,node.Lv,node.Rv);	}	int mid=(node.left+node.right)>>1;	if(ri<=mid) return query(id<<1,le,ri);	else if(le>mid) return query(id<<1|1,le,ri);	else{		Node a=query(id<<1,le,mid);		Node b=query(id<<1|1,mid+1,ri);		Node ans;		ans.Lv=a.Lv;		ans.Rv=b.Rv;		ans.sumL=a.sumL;		ans.sumR=b.sumR;		ans.sum=max(a.sum,b.sum);		if(a.Rv
      
       >1;	if(pos<=mid) update(id<<1,pos,val);	else update(id<<1|1,pos,val);	pushup(id);}int main(){	int T;	scanf("%d",&T);	while(T--){		scanf("%d%d",&n,&q);		for(int i=1;i<=n;++i) scanf("%d",&a[i]);		build(1,1,n);		while(q--){			char op[2];			int x,y;			scanf("%s%d%d",op,&x,&y);			if(op[0]=='U'){				update(1,x+1,y);			}			else{				int ans=query(1,x+1,y+1).sum;				printf("%d\n",ans);			}		}	}	return 0;}