【2025.2 省选模拟赛 1】LDS 做题记录

给定一个长 $n$ 的序列 $a$，你可以删除 $a$ 中的一些数，但相邻两个数不能被同时删除。设最后得到的序列为 $b$，你需要最小化 $b$ 的 LDS（最长严格下降子序列），输出这个最小的 LDS。

$1\le n\le 5\times 10^6$，$1\le a_i\le 21$。

原题：P11665 [JOI 2025 Final] 只不过是长的领带 2 / Just Long Neckties 2

首先考虑怎么求一个序列 $b$ 的 LDS，有两种方法：

• 设 $f_i$ 为以 $b_i$ 结尾的最长 LDS 的长度；
• 利用经典结论（LDS $\le x$ 相当于可以拆分成 $x$ 个 LNDS（最长不下降子序列））贪心，维护每个 LNDS 的最后一个数，每次对于所有能接的 LNDS，接末尾数最大的那个，若没有能接的则新开一个，LDS 增加 $1$；

第一个做法不太好维护，而对于第二个做法，不难发现任意时刻 LNDS 的末尾数字均两两不同，并且值域较小，故可以直接设状态 $f_{i,st}$ 表示处理完 $a_{[1,i]}$ 且保留了 $a_i$，LNDS 末尾数字集合为 $st$ 是否可行。转移是简单的。

考虑优化，对于这种 bool 类型的 dp，一个显然的思路是考虑增加信息量来减少复杂度（将某一维放进 dp 值里）。

挖掘性质：

• 随着转移的进行，$st$ 一定是越来越大的；
• 考虑将 $st$ 中为 $1$ 的位置写出来，即写下 LNDS 末尾数字的具体值且从小到大排序，设其为序列 $c$，则由该状态转移来的所有状态 $st'$ 对应的 $c'$ 一定都满足 $c\le c'$，故越转移状态越劣（更有可能使得 LDS 增加）；
• 那么对于每一个 $st$，只有最大的满足 $f_{i,st}=true$ 的 $i$ 是有用的，并且转移时也仅需要对每个 $st$ 保留当前最大的 $i$ 来转移。因为若最大 $i$ 无法转移到 $st'$，则此时 $st'$ 严格劣于 $st$（无法到达更远处且本身状态更劣）；

那么直接设 $f_{st}$ 表示 $st$ 最大的合法的 $i$ 即可，唯一的问题就是需要处理 $st\to st$ 的转移，因为加入本来就在 $st$ 中的值并不会改变 $st$，但却会使 $f_{st}$ 增加。那么考虑枚举使得该转移停止的 $(a_i,a_{i+1})$，显然要求这两个数均不在 $st$ 中，问题变为找到某个位置 $p$ 后第一个 $(a_i,a_{i+1})=(x,y)$ 的位置 $i$。这个可以直接 $O(nV^2)$ 预处理，但是空间开不下。

考虑分块优化空间，每 $50$ 个数分一块，预处理每一块到末尾的 $nxt_{x,y}$，这个可以在 $O(n+\frac{n}{50}V^2)$ 内完成。查询时先预处理好 $p$ 到其所在块末尾的 $nxt_{x,y}$，再去枚举 $(x,y)$ 并查询整块部分，这部分时间复杂度 $O(2^V(50+V^2))$，总时间复杂度 $O(n+\frac{n}{50}V^2+2^V(50+V^2))$，足以通过。

代码如下：

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>

using namespace std;

const int S=5000005,B=50,BS=1<<21;

int hb[BS];
int n,a[S];
int tmp[25][25],nxt[S/B+5][25][25];
int f[BS];

#define popc(x) __builtin_popcount(x)

inline int ins(int st,int x)
{
	int val=st&(1<<x)-1;
	if(val==0) st+=1<<x-1;
	else st=st-(1<<hb[val])+(1<<x-1);
	return st;
}

inline int quexy(int p,int x,int y)
{
	while(p<n&&p%B!=1)
	{
		if(min(a[p],a[p+1])==x&&max(a[p],a[p+1])==y) return p;
		p++;
	}
	if(p==n) return n+1;
	return nxt[(p+B)/B][x][y];
}

inline int que(int p,int st)
{
	if(p==n) return n+1;
	p++;
	int res=n+1;
	for(int i=1;i<=21;i++) for(int j=i;j<=21;j++) tmp[i][j]=n+1;
	int idx=(p-1)/B+1;
	int rb=min(n-1,idx*B);
	for(int i=rb;i>=p;i--)
	{
		int x=min(a[i],a[i+1]),y=max(a[i],a[i+1]);
		tmp[x][y]=i;
	}
	for(int x=1;x<=21;x++)
	{
		if(st>>x-1&1) continue;
		for(int y=x;y<=21;y++)
		{
			if(st>>y-1&1) continue;
			res=min(res,tmp[x][y]);
			if(idx*B+1<n) res=min(res,nxt[idx+1][x][y]);
		}
	}
	return res;
}

inline void tmax(int &x,int y){x=max(x,y);}

int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	for(int i=0;i<BS;i++) for(int j=0;j<21;j++) if(i>>j&1) hb[i]=j;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=21;i++) for(int j=i;j<=21;j++) tmp[i][j]=n+1;
	for(int i=n-1;i>=1;i--)
	{
		int x=min(a[i],a[i+1]),y=max(a[i],a[i+1]);
		tmp[x][y]=i;
		if(i%B==1) memcpy(nxt[(i+B)/B],tmp,sizeof(tmp));
	}
	memset(f,-1,sizeof(f));
	f[0]=0;
	int ans=21;
	for(int u=0;u<BS;u++)
	{
		int &i=f[u];
		if(i==-1) continue;
		i=que(i,u)-1;
		// cout<<u<<" "<<to<<endl;
		if(i<n) tmax(f[ins(u,a[i+1])],i+1);
		if(i<n-1) tmax(f[ins(u,a[i+2])],i+2);
		if(i==n-1||i==n) ans=min(ans,popc(u));
	}
	cout<<ans<<'\n';
	return 0;
}