自动搬运

查看原文

来自洛谷，原作者为

	ningago 恋爱脑

搬运于2025-08-24 22:51:08，当前版本为作者最后更新于2023-12-29 21:44:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前缀的字典序最小后缀问题，考虑 Lyndon 分解。称 Lyndon 分解的结果为 Lyndon 块，记第 $i$ 个 Lyndon 块为 $T_i$。

对于 $p_i$，根据定义有以下性质：

• $[p_i,i]$ 是 Lyndon 串。
• $[j,i](j<p_i)$ 不是 Lyndon 串。

也即，$p_i$ 为 $[1,i]$ 的所有后缀中最长的 Lyndon 串。

通过 $p_n$，可以得出 $n$ 所在的 Lyndon 分解的左端点 $l_n$，而通过 $p_{l_n-1}$ 可以得到下一个 Lyndon 分解的段。一直迭代下去，就可以通过 $p$ 求出原串的 Lyndon 分解。

令一个点 $i$ 所在的 Lyndon 块的左端点和右端点为 $l_i,r_i$。

考虑在 Duval 算法中，若 $j$ 是当前考虑的点，$k$ 是 $j$ 在已经求好的循环节中的对应点，则此时需要对 $s_j<s_k/s_j=s_k/s_j>s_k$ 进行讨论。

可以考虑模拟 Duval 算法：

• $s_j<s_k$，此时相当于划分 Lyndon 块，因为求出了 $l,r$，可以不管这种情况。（对每个块独立求解）
• $s_j>s_k$，此时相当于缩了一个大循环节，判断条件为 $p_j=l_j$。
• $s_j=s_k$，此时相当于让循环长度增加，判定条件为 $j-p_j=k-p_k$。
• 上述两条件都不满足，即为无解。

通过模拟 Duval 算法，可以求出：

• $pre_i$ 表示当 $j=i$ 时，对应的 $k$ 是谁。
• $val_i$ 表示是 $s_i=s_{pre_i}$ 还是 $s_i>s_{pre_i}$。令前者为 $0$ 后着为 $1$。

此时如果整个串只有一个 Lyndon 块，就可以根据条件从前往后字典序贪心（$val=0$ 就照抄，否则加一）。

而有多个 Lyndon 块时，新的条件为 $T_i\geq T_{i+1}$。

此时还是可以字典序贪心，但是按块 $T_i$ 从后往前（块内从前往后贪心）。

贪心时如果遇到当前位置比 $T_{i+1}$ 的对应位置小，分两种情况进行调整：

• 若 $val_i=1$，则可以直接照抄为 $T_{i+1}$ 的对应元素。
• 若 $val_i=0$，则需要让字典序在 $[1,i-1]$ 就定胜负，贪心的方法是：
  • 把上一个 $val_j=1$ 的点加一，然后将 $(j,i]$ 重新贪心分配字符（因为会对后面进行影响）。
• 由于进行一次第二种调整后，字典序就严格大于 $T_{i+1}$ 了，所以第二种调整每个块只会进行一次。复杂度是对的。

最后若 $T_i$ 是 $T_{i+1}$ 的严格前缀，也可以做第二种调整。

复杂度 $O(n)$。

代码参考了隔壁题解，Orz。

#define N 3000010
int n, m;
int p[N], last[N], s[N]; 
#define NO { printf("-1\n"); return; }
int pre[N]; bool val[N];
int lst(int x) { if(x > m) return 0; return last[x]; }
void solve()
{
	m = 0;
	n = read(); for(int i = 1; i <= n; i++) p[i] = read();
	for(int r = n, l; r >= 1; r = l - 1)
	{
		val[l = p[r]] = 1; for(int i = l; i <= r; i++) if(p[i] < l) NO;
		for(int i = l + 1, len = 1; i <= r; i++)
		{
			pre[i] = i - len;
			if(p[i] == l) { val[i] = 1; len = i - l + 1; }
			else if(i - p[i] == i - len - p[i - len]) val[i] = 0;
			else NO;
		}
		bool big = 0;
		s[l] = lst(1);
		for(int i = l + 1, j; i <= r; i++)
		{
			s[i] = s[pre[i]] + val[i];
			if(s[i] > lst(i - l + 1)) big = 1;
			if(!big && s[i] < lst(i - l + 1))
			{
				if(val[i]) s[i] = lst(i - l + 1);
				else { for(j = i; !val[j]; j--); s[i = j]++; big = 1; }
			}
		}
		if(!big && r - l + 1 < m)
		{
			int i, j;
			for(j = r; !val[j]; j--); s[i = j]++; big = 1;
			for(i++; i <= r; i++) s[i] = s[pre[i]] + val[i];
		}
		m = r - l + 1;
		for(int i = l; i <= r; i++) last[i - l + 1] = s[i];
	}
	for(int i = 1; i <= n; i++) print(s[i] + 1, ' '); putc('\n');
}