ABC240Ex Sequence of Substrings 做题记录

给定一个长度为 $n$ 的 01 串，求最多可以选出多少互不相交的子串，满足这些子串按照原串中的顺序，字典序严格升序。

$1\le n\le 2.5\times 10^4$。

不要再自然根号了。

设最终选出的子串为 $s_1,s_2,\dots,s_k$，则 $\forall 1\le i<k$，必定有 $|s_{i+1}|\le |s_i|+1$。

并且必定有 $|s_1|=1$。

那么不难得出， $\sum\limits_{i=1}^{\max\{|s_i|\}}i\le n$，因为对于所有 $i$ 都必定存在 $j$ 满足 $|s_j|=|s_i|-1$。

所以 $\max\{|s_i|\}\le \sqrt{2n}$。

那么设 $f_i$ 表示 $s_{[1,i]}$ 的答案，把所有长度 $\le \sqrt{2n}$ 的子串都拉出来放到 trie 上，用树状数组维护 $f_i$ 的转移即可。

答案即为 $\max\{f_i\}$，时间复杂度 $O(n\sqrt n\log n)$。

代码如下：

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

const int S=25005,M=250,MS=10000005;

int n;
char a[S];
int cnt,son[MS][2];
vector<pair<int,int>> idx[MS];
int c[S],f[S];

inline void addt(int u,int val)
{
	for(int i=u;i<=n;i+=i&-i) c[i]=max(c[i],val);
}

inline int quet(int u)
{
	int res=0;
	for(int i=u;i>=1;i-=i&-i) res=max(res,c[i]);
	return res;
}

void dfs(int u)
{
	for(auto u:idx[u])
	{
		int l=u.first,r=u.second;
		f[r]=max(f[r],quet(l-1)+1);
		addt(r,f[r]);
	}
	if(son[u][0]!=0) dfs(son[u][0]);
	if(son[u][1]!=0) dfs(son[u][1]);
}

int main()
{
	scanf("%d%s",&n,a+1);
	for(int i=n;i>=1;i--)
	{
		int u=0;
		for(int j=i;j<=n&&j<=i+M-1;j++)
		{
			int id=a[j]-'0';
			if(son[u][id]==0) son[u][id]=++cnt;
			u=son[u][id];
			idx[u].push_back({i,j});
		}
	}
	dfs(0);
	int ans=0;
	for(int i=1;i<=n;i++) ans=max(ans,f[i]);
	printf("%d\n",ans);
	return 0;
}