P5329 [SNOI2019] 字符串 题解

link T1です

听说这题以前是紫，看来难度也会随着时间贬值了呢。（虽然说也挺简单的）

遇到这种题目肯定是第一时间找规律的。

手玩一下可以发现，令 $b_j$ 表示第 $j$ 个连续同一字符的块，左右端点分别为 $b_{j,0}$，$b_{j,1}$。

那么 所有在这个块范围内的 $s$ 实际上都是一样的，即 $s_{b_{j,0}}=s_{b_{j,0}+1}=\dots=s_{b_{j,1}}$。

又可以想到，在后面删的所有情况，对于 $b_j$ 而言，其实是一样的。因为在 $b_{j,1}$ 之前的前缀是一样的。

从左往右考虑。那么在这个块内，只有删不删两种 $s$ 的集合。

当前块为字符 $c$。考虑删去时两个集合怎么排：

1. 如果说 $a_{b_{j,1}+1}>c$，那么删掉一个字符会使得 $a_{b_{j,1}+1}$ 进来，从而增大字典序。

   那么就需要将删去的 $s$ 全部排到后面。

   

2. 如果说 $a_{b_{j,1}+1}<c$，那么会减小字典序。那么就需要将删去的 $s$ 全部排到前面。

递归到下一个块即可。

int ans[maxn];
void solve(int l,int r,int i){
	if(l>r) return;
	int right=R[i],siz=R[i]-i+1;
	if(s[i]<s[right+1]){
		for(int j=i,k=r-siz+1;j<=right;++j,++k) ans[k]=j;
		solve(l,r-siz,right+1);
	}
	else{
		for(int j=i,k=l;j<=right;++j,++k) ans[k]=j;
		solve(l+siz,r,right+1);
	}
}