CF1468A LaIS 题解
首先可以写出这样一个方程
\[dp_i=\max_{j其中,\(w(i,j)=0/1\) 表示 \([i+1,j-1]\) 有没有比 \(a_i\) 和 \(a_j\) 都大的数。
考虑维护每个点的 \(pre\) 表示 \(\max_{a_j\geq a_i}\{j\}\),这样上面那个 dp 相当于
\[dp_i=\max(\max_{j用线段树维护 dp 值,这相当于查历史版本的区间 \(\max\),使用可持久化线段树做即可,也可以离线之后扫描线。
code by CCCCOrz:
点击查看代码
#include
#include using namespace std; inline int rd(){ register int x=0; register char c=getchar(); while(c<'0'||c>'9')c=getchar(); while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x; } inline int mmax(const int &x,const int &y){return x>y?x:y;} int n,cnt,a[500010],dp[500010],to[500010],pre[500010],rt[500010],ans,tot; struct node{ int ls,rs,mx; }t[10000010]; struct qd{ int val,at; inline bool operator <(const qd &x)const{ return val>x.val; } }; inline int qus(int l,int r,int p,const int &e){ if(e>=r)return t[p].mx; int mid=l+r>>1,ans=qus(l,mid,t[p].ls,e); if(e>mid)ans=mmax(ans,qus(mid+1,r,t[p].rs,e)); return ans; } inline int ist(int l,int r,int p,const int &w,const int &val){ if(l==r){ t[++tot]=(node){0,0,val}; return tot; } int mid=l+r>>1,nw=++tot; if(w<=mid){ t[nw].ls=ist(l,mid,t[p].ls,w,val); t[nw].rs=t[p].rs; } else{ t[nw].ls=t[p].ls; t[nw].rs=ist(mid+1,r,t[p].rs,w,val); } t[nw].mx=mmax(t[t[nw].ls].mx,t[t[nw].rs].mx); return nw; } int main(){ cnt=rd(); while(cnt--){ n=rd(),tot=0,ans=0; for(int i=1;i<=n;++i)a[i]=rd(),pre[i]=0; priority_queue q; for(int i=n;i;--i){ q.push((qd){a[i],i}); while(a[i]>q.top().val) pre[q.top().at]=i,q.pop(); } dp[1]=1,rt[1]=ist(1,n,0,a[1],1); for(int i=2;i<=n;++i){ dp[i]=mmax(qus(1,n,rt[pre[i]],a[i])+2,qus(1,n,rt[i-1],a[i])+1); rt[i]=ist(1,n,rt[i-1],a[i],dp[i]); ans=mmax(ans,dp[i]); } printf("%d\n",ans); } return 0; }