给定 和一个 的排列 ,考虑以下过程:
维护一个初始为空的栈,然后从 到 枚举 :
- 比栈顶严格大或栈为空,那么把 加入栈中;
- 否则:
- 把栈顶弹出,并把 加入栈中。注意,你需要保证操作完成后栈中元素从底到顶严格单调递增;
- 什么也不干;
请你求出最后栈大小的最大值。
。
首先若设 nxt_i=\min\{j|j>i\and a_j>a_i\}, 表示以 结尾且最终序列包含 的最长子序列长度,那么 能转移到 当且仅当 且 。
考虑消除 这个限制,一种巧妙的做法是按照 从小到大枚举 。消掉限制后直接用线段树维护转移即可。
代码如下:
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int S=500005;
int n,a[S],pos[S];
int top,sta[S];
int nxt[S];
int tag[S<<2],mx[S<<2],dp[S];
inline void addtag(int u,int val)
{
tag[u]=max(tag[u],val),mx[u]=max(mx[u],val);
}
inline void dwntag(int u)
{
addtag(u<<1,tag[u]),addtag(u<<1|1,tag[u]);
tag[u]=-1e8;
}
void upd(int u,int l,int r,int L,int R,int val)
{
if(l>R||r<L) return;
if(l>=L&&r<=R)
{
addtag(u,val);
return;
}
dwntag(u);
int mid=l+r>>1;
if(L<=mid) upd(u<<1,l,mid,L,R,val);
if(R>=mid+1) upd(u<<1|1,mid+1,r,L,R,val);
mx[u]=max(mx[u<<1],mx[u<<1|1]);
}
int que(int u,int l,int r,int pos)
{
if(l==r) return mx[u];
dwntag(u);
int mid=l+r>>1;
if(pos<=mid) return que(u<<1,l,mid,pos);
else return que(u<<1|1,mid+1,r,pos);
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]),pos[a[i]]=i;
pos[a[0]=0]=0;
sta[top=0]=n+1;
for(int i=n;i>=0;i--)
{
while(top>0&&a[sta[top]]<a[i]) top--;
nxt[i]=sta[top];
sta[++top]=i;
}
memset(mx,128,sizeof(mx));
memset(tag,128,sizeof(tag));
for(int i=0;i<=n;i++)
{
int id=pos[i];
int lb=nxt[id],rb=nxt[nxt[id]]-1;
dp[id]=id==0?0:que(1,1,n,id);
if(lb>rb) continue;
if(lb<1||rb>n) continue;
upd(1,1,n,lb,rb,dp[id]+1);
}
int ans=0;
for(int i=1;i<=n;i++) ans=max(ans,dp[i]);
printf("%d\n",ans);
return 0;
}