【Public Judge NOIP Round 2】排序 做题记录

给定 nn 和一个 nn 的排列 aa,考虑以下过程:

维护一个初始为空的栈,然后从 11nn 枚举 ii

  • aia_i 比栈顶严格大或栈为空,那么把 aia_i 加入栈中;
  • 否则:
    • 把栈顶弹出,并把 aia_i 加入栈中。注意,你需要保证操作完成后栈中元素从底到顶严格单调递增;
    • 什么也不干;

请你求出最后栈大小的最大值。

1n5×1051\le n\le 5\times 10^5

首先若设 nxt_i=\min\{j|j>i\and a_j>a_i\}dpidp_i 表示以 aia_i 结尾且最终序列包含 aia_i 的最长子序列长度,那么 dpi+1dp_i+1 能转移到 dpjdp_j 当且仅当 j[nxti,nxtnxti1]j\in[nxt_i,nxt_{nxt_i}-1]aj>aia_j>a_i

考虑消除 aj>aia_j>a_i 这个限制,一种巧妙的做法是按照 aia_i 从小到大枚举 ii。消掉限制后直接用线段树维护转移即可。

代码如下:

#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;
}