3308 LCIS(线段树水题&最长连续递增序列)

LCISTime Limit: 6000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 3261 Accepted Submission(s): 1438


Problem DescriptionInputOutputSample InputSample OutputAuthorSourceRecommend#include<algorithm>#include<iostream>#include<string.h>#include<sstream>#include<stdio.h>#include<math.h>#include<vector>#include<string>#include<queue>#include<set>#include<map>using namespace std;const int INF=0x3f3f3f3f;const int maxn=100010;int ml[maxn<<2],mr[maxn<<2],ma[maxn<<2];int val[maxn];void pushup(int L,int R,int k){ int ls,rs,mid; ls=k<<1; rs=ls|1; mid=(L+R)>>1; ma[k]=max(ma[ls],ma[rs]); ml[k]=ml[ls]; mr[k]=mr[rs]; if(val[mid+1]>val[mid]) { if(ml[ls]==mid-L+1) ml[k]+=ml[rs]; if(mr[rs]==R-mid) mr[k]+=mr[ls]; ma[k]=max(ma[k],mr[ls]+ml[rs]); }}void btree(int L,int R,int k){ int ls,rs,mid; if(L==R) { scanf("%d",&val[L]); ml[k]=mr[k]=ma[k]=1; return; } ls=k<<1; rs=ls|1; mid=(L+R)>>1; btree(L,mid,ls); btree(mid+1,R,rs); pushup(L,R,k);}void update(int L,int R,int p,int k,int d){ int ls,rs,mid; if(L==R) { val[L]=d; return; } ls=k<<1; rs=ls|1; mid=(L+R)>>1; if(p>mid) update(mid+1,R,p,rs,d); else update(L,mid,p,ls,d); pushup(L,R,k);}int qu(int L,int R,int l,int r,int k){ int ls,rs,mid,a,b,ans; if(l==L&&r==R) return ma[k]; ls=k<<1; rs=ls|1; mid=(L+R)>>1; if(l>mid) return qu(mid+1,R,l,r,rs); else if(r<=mid) return qu(L,mid,l,r,ls); else { ans=max(qu(L,mid,l,mid,ls),qu(mid+1,R,mid+1,r,rs)); if(val[mid+1]>val[mid]) { a=min(mid-l+1,mr[ls]);//注意下这就行了。 b=min(r-mid,ml[rs]); return max(ans,a+b); } return ans; }}int main(){ int t,n,m,a,b; char com[10]; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); btree(1,n,1); while(m--) { scanf("%s%d%d",com,&a,&b); if(com[0]=='U') { a++; update(1,n,a,1,b); } else { a++,b++; printf("%d\n",qu(1,n,a,b,1)); } } } return 0;}