题意：给你n个整数，有两种操作，U A B把第A个数变成B，Q A B查询区间[A,B]的最长连续上升序列。
本题中的递推关系是：
1. 左儿子最右边的值 < 右儿子最左边的值 lmx = (左儿子的lmx == 左儿子的len) ? 左儿子的len + 右儿子的lmx : 左儿子的lmx; rmx = (右儿子的rmx == 右儿子的len) ? 右儿子的len + 左儿子的rmx : 右儿子的rmx; mx = MAX(左儿子的rmx + 右儿子的lmx, 左儿子的mx, 右儿子的mx, 自身的lmx, 自身的rmx);2. 左儿子最右边的值 >= 右儿子最左边的值 lmx = 左儿子的lmx; rmx = 右儿子的rmx; mx = MAX(左儿子的mx, 右儿子的mx);
在查询的时候，有个注意点，如果查询的范围是在当前区间的左右儿子里，并且左儿子的右端点小于右儿子的左端点，那么不能直接取左儿子的rmx加上右儿子的lmx，因为有可能查询的范围的长度就已经小于左儿子的rmx加上右儿子的lmx，所以要加上一个判断。
学习了大神的代码风格。
用结构体封装了整个线段树的所有函数
用结构体封装了线段树每个结点里面要记录的内容和一些常用的函数（算中点，，算区间长度）
这样线段树就格式化了…233..而且添加要记录的内容也变得清晰方便，比如这题可以在结点里面加个lval和rval记录区间左右端点对应的值，因题而异，清晰灵活。
//280MS 8676K#include<cstdio>#include<cstring>#include<algorithm>#include<iostream>using namespace std;const int M=1e5+5;#define LL(x) (x<<1) //左儿子序号#define RR(x) (x<<1|1) //右儿子序号#define MID(a,b) (a+((b-a)>>1) ) //小技巧int num[M],n,m;struct node //线段树的结点内容{int l,r;int lval,rval; //区间左右端点对应的num[i]int lmx,rmx,mx; //区间合并的三巨头(基础)int mid(){return MID(l,r);}int len(){return r-l+1;}};struct Segtree //封装线段树的全部函数{node tree[M<<2];void up(int rt){tree[rt].lval=tree[LL(rt)].lval;tree[rt].rval=tree[RR(rt)].rval;tree[rt].lmx= tree[LL(rt)].lmx;tree[rt].rmx= tree[RR(rt)].rmx;tree[rt].mx=-1; //别丢了，多组数据要初始化，开始就wa了一次if(tree[LL(rt)].rval<tree[RR(rt)].lval){if(tree[rt].lmx==tree[LL(rt)].len())tree[rt].lmx+=tree[RR(rt)].lmx;if(tree[rt].rmx==tree[RR(rt)].len())tree[rt].rmx+=tree[LL(rt)].rmx;tree[rt].mx = tree[LL(rt)].rmx + tree[RR(rt)].lmx;}tree[rt].mx=max(tree[rt].mx,max( max(tree[LL(rt)].mx,tree[RR(rt)].mx),max(tree[rt].lmx,tree[rt].rmx) ));//这步是递推关系式要考虑全多种情况}void build(int l,int r,int rt){tree[rt].l=l;tree[rt].r=r;if(l==r){tree[rt].lval=tree[rt].rval=num[l];tree[rt].lmx=tree[rt].rmx=tree[rt].mx=1;return ;}int m= tree[rt].mid();build(l,m,LL(rt));build(m+1,r,RR(rt));up(rt);}void update(int pos,int rt,int val){if(tree[rt].l==tree[rt].r){tree[rt].lval=tree[rt].rval=val;tree[rt].lmx=tree[rt].rmx=tree[rt].mx=1;return ;}int m=tree[rt].mid();if(pos<=m) update(pos,LL(rt),val);else update(pos,RR(rt),val);up(rt);}int query(int st,int ed,int rt){if(st<=tree[rt].l&&tree[rt].r<=ed){return tree[rt].mx;}int m = tree[rt].mid();if(ed<=m) return query(st,ed,LL(rt));if(st>m) return query(st,ed,RR(rt));int mx1=query(st,ed,LL(rt));int mx2=query(st,ed,RR(rt));if(tree[LL(rt)].rval<tree[RR(rt)].lval ){int m=tree[rt].mid();int t1=min(tree[LL(rt)].rmx,m-st+1 );int t2=min(tree[RR(rt)].lmx,ed-m);return max(max(mx1,mx2),t1+t2); //查询也要考虑多种情况防止遗漏}else return max(mx1,mx2);}}seg;int main(){int T;scanf("%d",&T);while(T–){scanf("%d%d",&n,&m);for(int i=0;i<n;i++) scanf("%d",&num[i]);seg.build(0,n-1,1);while(m–){char op[5];int a,b;scanf("%s%d%d",op,&a,&b);if(op[0]=='U'){seg.update(a,1,b);}else printf("%d\n",seg.query(a,b,1));}}return 0;}
就是去做你害怕的事，直到你获得成功的经验。
