hdu 3308 LCIS(线段树区间合并)
题意：给一个序列，有两种操作，Q：询问x到y的LCIS长度。U：将序号为x的值改为y。
思路：用线段树来维护序列，每次更改值时就更新树，查询是很快的，查询时要注意。
#include<stdio.h>#include<string.h>const int N=100100;int a[N];struct Tree{int L,R,ml;int Ll,Rl,Ln,Rn;//ml区间的LCIS长度//Ll,Rl区间左边右边的LCIS长度//Ln,Rn区间左右的值}T[N*3];int max(int a,int b){if(a>b)return a;return b;}int min(int a,int b){if(a<b)return a;return b;}void buildTree(int L,int R,int id){T[id].L=L;T[id].R=R;if(L==R){T[id].Ln=T[id].Rn=a[L];T[id].ml=T[id].Ll=T[id].Rl=1;return ;}int mid=(L+R)>>1,li=id<<1,ri=li+1;buildTree(L,mid,id<<1);buildTree(mid+1,R,id<<1|1);T[id].Ln=T[li].Ln;T[id].Rn=T[ri].Rn;T[id].Ll=T[li].Ll;T[id].Rl=T[ri].Rl;T[id].ml=max(T[li].ml,T[ri].ml);if(T[li].Rn<T[ri].Ln)//左区间和右区间可以合并{T[id].ml=max(T[id].ml,T[li].Rl+T[ri].Ll);if(T[li].Rl==mid-T[li].L+1)//左区间整个区间是LCIS，更新该区间的左边LCIS长度。T[id].Ll=T[li].Ll+T[ri].Ll;if(T[ri].Rl==T[ri].R-mid)T[id].Rl=T[li].Rl+T[ri].Rl;}}void insert(int LR,int w,int id){if(T[id].L==T[id].R){T[id].Ln=T[id].Rn=w;return ;}int mid=(T[id].L+T[id].R)>>1,li=id<<1,ri=li+1;if(LR<=mid)insert(LR,w,li);else insert(LR,w,ri);T[id].Ln=T[li].Ln;T[id].Rn=T[ri].Rn;T[id].Ll=T[li].Ll;T[id].Rl=T[ri].Rl;T[id].ml=max(T[li].ml,T[ri].ml);if(T[li].Rn<T[ri].Ln){T[id].ml=max(T[id].ml,T[li].Rl+T[ri].Ll);if(T[li].Rl==mid-T[li].L+1)T[id].Ll=T[li].Ll+T[ri].Ll;if(T[ri].Rl==T[ri].R-mid)T[id].Rl=T[li].Rl+T[ri].Rl;}}int query(int L,int R,int id){if(T[id].L==L&&T[id].R==R)return T[id].ml;int mid=(T[id].L+T[id].R)>>1,li=id<<1,ri=li+1;if(mid>=R)return query(L,R,li);else if(mid<L) return query(L,R,ri);else {int ls=query(L,mid,li);int rs=query(mid+1,R,ri);int ps=0;if(T[li].Rn<T[ri].Ln)//左右两区间可以合并ps=min(mid-L+1,T[li].Rl)+min(R-mid,T[ri].Ll);//合并的长度return max(ps,max(ls,rs));}}int main(){int i,x,y,n,m,t;char str[10];scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);for(i=1;i<=n;i++)scanf("%d",&a[i]);buildTree(1,n,1);while(m--){scanf("%s%d%d",str,&x,&y);if(str[0]=='Q')printf("%d\n",query(x+1,y+1,1));else insert(x+1,y,1);}}return 0;}