Problem Description Given n integers. You have two operations: U A B: replace the Ath number by B. (index counting from 0) Q A B: output the length of the longest consecutive increasing subsequence (LCIS) in [a, b].
Input T in the first line, indicating the case number. Each case starts with two integers n , m(0< n,m<=105). The next line has n integers(0<=val<=105). The next m lines each has an operation: U A B(0<=A,n , 0<=B=105) OR Q A B(0<=A<=B< n).
Output For each Q, output the answer.
线段树维护即可。每个节点维护最大长度、从左起最大长度和从右起最大长度。和 SPOJ GSS1 Can you answer these queries I 【见这里】有异曲同工之处。
#include<cstdio> #include<cstring> int a[100010],lson[400010],rson[400010],ans[400010],lans[400010],rans[400010],m,n,tot; int max(int x,int y) { return x>y?x:y; } void build(int p,int l,int r) { if (l==r) { lson[p]=rson[p]=0; ans[p]=lans[p]=rans[p]=1; return; } int i,j,k,x,y,z,mid; mid=(l+r)/2; lson[p]=++tot; build(tot,l,mid); rson[p]=++tot; build(tot,mid+1,r); if (lans[lson[p]]==mid-l+1&&a[mid]<a[mid+1]) lans[p]=mid-l+1+lans[rson[p]]; else lans[p]=lans[lson[p]]; if (rans[rson[p]]==r-mid&&a[mid]<a[mid+1]) rans[p]=r-mid+rans[lson[p]]; else rans[p]=rans[rson[p]]; ans[p]=max(max(lans[p],rans[p]),max(ans[lson[p]],ans[rson[p]])); if (a[mid]<a[mid+1]) ans[p]=max(ans[p],rans[lson[p]]+lans[rson[p]]); } void query(int p,int ll,int rr,int l,int r,int &mx,int &lmx,int &rmx) { if (ll==l&&rr==r) { mx=ans[p]; lmx=lans[p]; rmx=rans[p]; return; } int i,j,k,x,y,z,mid,l_mx,l_lmx,l_rmx,r_mx,r_lmx,r_rmx; mid=(ll+rr)/2; if (r<=mid) { query(lson[p],ll,mid,l,r,mx,lmx,rmx); return; } if (l>=mid+1) { query(rson[p],mid+1,rr,l,r,mx,lmx,rmx); return; } query(lson[p],ll,mid,l,mid,l_mx,l_lmx,l_rmx); query(rson[p],mid+1,rr,mid+1,r,r_mx,r_lmx,r_rmx); if (l_lmx==mid-l+1&&a[mid]<a[mid+1]) lmx=mid-l+1+r_lmx; else lmx=l_lmx; if (r_rmx==r-mid&&a[mid]<a[mid+1]) rmx=r-mid+l_rmx; else rmx=r_rmx; mx=max(max(lmx,rmx),max(l_mx,r_mx)); if (a[mid]<a[mid+1]) mx=max(mx,l_rmx+r_lmx); } void modify(int p,int ll,int rr,int x) { if (ll==rr) return; int i,j,k,mid; mid=(ll+rr)/2; if (x<=mid) modify(lson[p],ll,mid,x); else modify(rson[p],mid+1,rr,x); if (lans[lson[p]]==mid-ll+1&&a[mid]<a[mid+1]) lans[p]=mid-ll+1+lans[rson[p]]; else lans[p]=lans[lson[p]]; if (rans[rson[p]]==rr-mid&&a[mid]<a[mid+1]) rans[p]=rr-mid+rans[lson[p]]; else rans[p]=rans[rson[p]]; ans[p]=max(max(lans[p],rans[p]),max(ans[lson[p]],ans[rson[p]])); if (a[mid]<a[mid+1]) ans[p]=max(ans[p],rans[lson[p]]+lans[rson[p]]); } int main() { int i,j,k,x,y,z,T,lmx,rmx,mx; char s[5]; scanf("%d",&T); while (T--) { tot=1; scanf("%d%d",&n,&m); for (i=0;i<n;i++) scanf("%d",&a[i]); build(1,0,n-1); for (i=1;i<=m;i++) { scanf("%s%d%d",s,&x,&y); if (s[0]=='Q') { query(1,0,n-1,x,y,mx,lmx,rmx); printf("%d\n",mx); } else { a[x]=y; modify(1,0,n-1,x); } } } }