P9719 [EC Final 2022] Minimum Suffix

ningago · 2023-12-29 21:44:06 · 题解

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

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

也即，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 算法：

• 上述两条件都不满足，即为无解。

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

此时如果整个串只有一个 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');
}