HDU 3308 LCIS(线段树，连续递增子)
转载请注明出处，谢谢http://blog.csdn.net/acm_cxlove/article/details/7854526 by---cxlove
题目：给出一个序列，两种操作，单点更新值，以及查询区间的最长连续递增子序列长度
http://acm.hdu.edu.cn/showproblem.php?pid=3308
这题比较简单，如果是求最长递增子序列长度就难了，不需要连续就是简单的区间合并类的线段树了。
每一个结点要记录包含左端点的最长连续递增子长度，包含右端点的最长连续递增子长度，以及整个区间的最长递增子长度，典型的区间合并问题。
向上更新部分要注意细节
对于左连续的话，可以由左孩子的左连续得来，但是可能包括右孩子的左连续，要进行判断左孩子的左连续是否是整个区间，而且中间的结合是否满足递增
右连续一样。
对于整个区间的最值，可能来源与左右孩子的最值，也可以来源于两个区间的中间部分。
更新部分不需要解释，直接更新到叶子节点，然后通过子节点更新父节点
查询的时候有点麻烦，需要区间合并的时候需要格外注意
左右孩子分别找的结果，以及可能是 两个区间的合并，但是要注意细节
#include<iostream>#include<fstream>#include<iomanip>#include<cstdio>#include<cstring>#include<algorithm>#include<cstdlib>#include<cmath>#include<set>#include<map>#include<queue>#include<stack>#include<string>#include<vector>#include<ctime>#include<sstream>#include<cassert>#define LL long long#define eps 1e-7#define zero(a) fabs(a)<eps#define inf 1<<30#define N 100005#define pi acos(-1.0)#define pb(a) push_back(a)#define lson step<<1#define rson step<<1|1using namespace std;struct SegmentTree{ int left,right,mid; int mx,lx,rx; int dist(){return right-left+1;}}L[N*4];int a[N];void Push_Up(int step){ L[step].lx=L[lson].lx+((L[lson].lx==L[lson].dist()&&a[L[rson].left]>a[L[lson].right])?L[rson].lx:0); L[step].rx=L[rson].rx+((L[rson].rx==L[rson].dist()&&a[L[rson].left]>a[L[lson].right])?L[lson].rx:0); L[step].mx=max(max(L[lson].mx,L[rson].mx),a[L[rson].left]>a[L[lson].right]?(L[lson].rx+L[rson].lx):0);}void Bulid(int step,int l,int r){ L[step].left=l; L[step].right=r; L[step].mid=(l+r)/2; if(l==r){ L[step].lx=L[step].rx=L[step].mx=1; return; } Bulid(lson,l,L[step].mid); Bulid(rson,L[step].mid+1,r); Push_Up(step);}void Update(int step,int pos,int k){ if(L[step].left==L[step].right){ L[step].lx=L[step].rx=L[step].mx=1; return ; } if(pos<=L[step].mid) Update(lson,pos,k); else Update(rson,pos,k); Push_Up(step);}int Query(int step,int l,int r){ if(l==L[step].left&&r==L[step].right) return L[step].mx; if(r<=L[step].mid) return Query(lson,l,r); else if(l>L[step].mid) return Query(rson,l,r); else{ int ltmp=Query(lson,l,L[step].mid); int rtmp=Query(rson,L[step].mid+1,r); int sum=0; if(a[L[rson].left]>a[L[lson].right]) sum=min(L[step].mid-l+1,L[lson].rx)+min(r-L[step].mid,L[rson].lx); return max(max(ltmp,rtmp),sum); }}int main(){ int t,n,m,l,r; char str[10]; scanf("%d",&t); while(t--){ scanf("%d%d",&n,&m); for(int i=0;i<n;i++) scanf("%d",&a[i]); Bulid(1,0,n-1); // for(int i=1;i<=30;i++) // printf("%d %d %d %d %d\n",L[i].left,L[i].right,L[i].mx,L[i].lx,L[i].rx); while(m--){ scanf("%s%d%d",str,&l,&r); if(str[0]=='Q') printf("%d\n",Query(1,l,r)); else {a[l]=r;Update(1,l,r);} } } return 0;}