hdu3308LCIS(线段树，点更新，段查寻，查寻时一定要注意跨越时如何计算)
Problem DescriptionInputOutputSample InputSample Output#include<stdio.h>#define N 500010struct node{ int Llcis,Rlcis,lcis;//最左连续升序长度，最右连续升序长度，这个范围的最长连续升序长度}tree[8*N];int num[N+5];int max(int a,int b){ return a>b?a:b;}void chang_tree(int l,int r,int k)//根据第K个节点的左右节点,计算第K个节点的最左，最右和最长 的升序长度{ int m=(l+r)/2; node ltree=tree[k*2],rtree=tree[k*2+1]; if(num[m]>=num[m+1])//当左节点的最右边的值不小右节点的最左边的值时 { tree[k].Llcis=ltree.Llcis; tree[k].Rlcis=rtree.Rlcis; tree[k].lcis=max(ltree.lcis,rtree.lcis); } else { if(m-l+1==ltree.Llcis) tree[k].Llcis=ltree.Llcis+rtree.Llcis; else tree[k].Llcis=ltree.Llcis; if(r-m==rtree.Rlcis) tree[k].Rlcis=rtree.Rlcis+ltree.Rlcis; else tree[k].Rlcis=rtree.Rlcis; tree[k].lcis=max(ltree.lcis,ltree.Rlcis+rtree.Llcis); tree[k].lcis=max(tree[k].lcis,rtree.lcis); tree[k].lcis=max(tree[k].lcis,tree[k].Llcis); tree[k].lcis=max(tree[k].lcis,tree[k].Rlcis); }}void build(int l,int r,int k){ int m=(l+r)/2; if(l==r){ tree[k].Llcis=1; tree[k].lcis=1; tree[k].Rlcis=1; return ; } build(l,m,k*2); build(m+1,r,k*2+1); chang_tree(l,r,k);}void updata(int l,int r,int k,int Q,int ans){ int m=(l+r)/2; if(l==Q&&Q==r) {num[Q]=ans; return ;} if(Q<=m) updata(l,m,k*2,Q,ans); if(Q>m) updata(m+1,r,k*2+1,Q,ans); chang_tree(l,r,k);}int maxlen;void find(int l,int r,int k,int L,int R){ int m=(l+r)/2; if(L<=l&&r<=R){ maxlen=max(tree[k].lcis,maxlen); return ; } if(R<=m) find(l,m,k*2,L,R); else if(L>m) find(m+1,r,k*2+1,L,R); else{ find(l,m,k*2,L,R); find(m+1,r,k*2+1,L,R); //-----当查寻夸越左右子树时,左子树的最右端点的值小于右子树的最左端点的值------ if(num[m]<num[m+1]) if(L<=m-tree[2*k].Rlcis+1&&m+tree[k*2+1].Llcis<=R)//注意这个条件 maxlen=max(tree[k*2].Rlcis+tree[k*2+1].Llcis,maxlen); else if(L<=m-tree[2*k].Rlcis+1&&m+tree[k*2+1].Llcis>R)//注意这个条件 maxlen=max(tree[k*2].Rlcis+R-m,maxlen); else if(L>m-tree[2*k].Rlcis+1&&m+tree[k*2+1].Llcis<=R)//注意这个条件 maxlen=max(m-L+1+tree[k*2+1].Llcis,maxlen); else maxlen=R-L+1;//最长的升序长度 }}int main(){ int t,n,m,QL,QR; char c[2]; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&num[i]); build(1,n,1); while(m--) { scanf("%s%d%d",c,&QL,&QR); if(c[0]=='U') updata(1,n,1,QL+1,QR); if(c[0]=='Q') { maxlen=0; find(1,n,1,QL+1,QR+1); printf("%d\n",maxlen); } } }}
