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].
【题目分析】 线段树裸题，有点像SPOJ GSS1.
【代码】
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; int n,m,data[100001],a,b; char ch[31]; struct node{int l,r,lans,rans,mans;}t[400001]; inline node query(int k,int l,int r) { // cout<<k<<endl; if (t[k].l>=l&&t[k].r<=r) return t[k]; node now,nowl,nowr; int mid=(t[k].l+t[k].r)/2; if (r<=mid) return query(k*2,l,r); if (l>=mid+1) return query(k*2+1,l,r); nowl=query(k*2,l,r);nowr=query(k*2+1,l,r); now.l=nowl.l,now.r=nowr.r; now.lans=nowl.lans; if (nowl.lans==(nowl.r-nowl.l+1)) if (data[nowl.r]<data[nowr.l]) now.lans=nowl.lans+nowr.lans; now.rans=nowr.rans; if (nowr.rans==(nowr.r-nowr.l+1)) if (data[nowl.r]<data[nowr.l]) now.rans=nowr.rans+nowl.rans; now.mans=max(nowl.mans,nowr.mans); now.mans=max(max(now.lans,now.rans),now.mans); if (data[nowl.r]<data[nowr.l]) now.mans=max(nowl.rans+nowr.lans,now.mans); return now; } inline void updata(int k,int pos,int L,int R) { if (L==R) return ; int mid=(t[k].l+t[k].r)/2; if (pos<=mid) updata(k*2,pos,L,(L+R)/2); else updata(k*2+1,pos,(L+R)/2+1,R); t[k].lans=t[k*2].lans; if (t[k*2].lans==(t[k*2].r-t[k*2].l+1)) if (data[(L+R)/2]<data[(L+R)/2+1]) t[k].lans=t[k*2].lans+t[k*2+1].lans; t[k].rans=t[k*2+1].rans; if (t[k*2+1].rans==(t[k*2+1].r-t[k*2+1].l+1)) if (data[(L+R)/2]<data[(L+R)/2+1]) t[k].rans=t[k*2+1].rans+t[k*2].rans; t[k].mans=max(t[k*2].mans,t[k*2+1].mans); t[k].mans=max(max(t[k].lans,t[k].rans),t[k].mans); if (data[(L+R)/2]<data[(L+R)/2+1]) t[k].mans=max(t[k*2].rans+t[k*2+1].lans,t[k].mans); } inline void build(int k,int L,int R) { t[k].l=L;t[k].r=R; if (L==R) {t[k].lans=t[k].rans=t[k].mans=1;return;} build(k*2,L,(L+R)/2); build(k*2+1,(L+R)/2+1,R); t[k].lans=t[k*2].lans; if (t[k*2].lans==(t[k*2].r-t[k*2].l+1)) if (data[(L+R)/2]<data[(L+R)/2+1]) t[k].lans=t[k*2].lans+t[k*2+1].lans; t[k].rans=t[k*2+1].rans; if (t[k*2+1].rans==(t[k*2+1].r-t[k*2+1].l+1)) if (data[(L+R)/2]<data[(L+R)/2+1]) t[k].rans=t[k*2+1].rans+t[k*2].rans; t[k].mans=max(t[k*2].mans,t[k*2+1].mans); t[k].mans=max(max(t[k].lans,t[k].rans),t[k].mans); if (data[(L+R)/2]<data[(L+R)/2+1]) t[k].mans=max(t[k*2].rans+t[k*2+1].lans,t[k].mans); } int main() { int tt; scanf("%d",&tt); while (tt--) { scanf("%d%d",&n,&m); for (int i=1;i<=n;++i) scanf("%d",&data[i]); // for (int i=1;i<=n;++i) data[i]=i; build(1,1,n); // cout<<t[2].lans<<" "<<t[2].rans<<" "<<t[2].mans<<endl; for (int i=1;i<=m;++i) { scanf("%s",ch); scanf("%d%d",&a,&b); if (ch[0]=='Q') printf("%d\n",query(1,a+1,b+1).mans); else {data[a+1]=b;updata(1,a+1,1,n);} // for (int i=1;i<50;++i) cout<<t[i].lans<<" "<<t[i].rans<<" "<<t[i].mans<<endl; } // for (int i=1;i<=n;++i) cout<<data[i]<<" "; } }