[EC Final 2022] Minimum Suffix

形式化题目

给定长度为 $n$ 的正整数序列 $s$ （整数越小代表字符越小）。对每个 $j$ ，定义 $p_j = x$ 当且仅当 $s[x\ldots j]$ 是 $s[1\ldots j]$ 的所有后缀中字典序最小者。

现在只给出 $p_1,\ldots,p_n$ ，要求构造一个满足该 $p$ 的序列 $s$ ；若有多解，取字典序最小者；若无解则报告无解。

暴力解法

思路

题目要求的答案是一个「字符」序列，而字符之间只有相对大小关系有意义，所以最优解一定可以只使用 $1,2,\ldots,n$ 这些整数。

于是最朴素的做法就是：按字典序从小到大枚举所有长度为 $n$ 、字符取值在 $[1,n]$ 的序列，对每个序列按定义算出它的 $p$ 数组，与输入比对；第一个匹配上的就是字典序最小的答案。枚举顺序天然保证我们找到的是最小解。

按定义求 $p$ 时，直接对每个 $j$ 枚举所有后缀 $s[x\ldots j]$ ，两两比较字典序取最小即可。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-02 15:23
 * update_at: 2026-10-02 15:23
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
// 做法：答案只依赖字符之间的相对大小，所以最优解一定可以只使用 1..n 这些字符。
//       枚举所有 s[1..n]（按字典序升序），第一个满足 p 的即为字典序最小的答案。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10;

int n;
int p[MAXN];    // 输入的 p_i
int cur[MAXN];  // 当前枚举的串
int ans[MAXN];  // 找到的答案
bool found;

// 计算当前串 cur 的 p 数组，与输入比较
bool check() {
    for (int j = 1; j <= n; ++j) {
        // 在 s[1..j] 的所有后缀中找字典序最小者（后缀长度互不相同，最小值唯一）
        int best = 1;
        for (int x = 2; x <= j; ++x) {
            // 比较 s[x..j] 与 s[best..j]
            int i = x, k = best;
            while (i <= j && k <= j && cur[i] == cur[k]) {
                ++i;
                ++k;
            }
            if (k > j) {
                // s[best..j] 是 s[x..j] 的前缀，更短的后缀字典序更小
                continue;
            }
            if (i > j) {
                // s[x..j] 是 s[best..j] 的前缀，更小
                best = x;
                continue;
            }
            if (cur[i] < cur[k]) best = x;
        }
        if (best != p[j]) return false;
    }
    return true;
}

// 按字典序枚举所有串
void dfs(int dep) {
    if (found) return;
    if (dep > n) {
        if (check()) {
            found = true;
            for (int i = 1; i <= n; ++i) ans[i] = cur[i];
        }
        return;
    }
    for (int c = 1; c <= n && !found; ++c) {
        cur[dep] = c;
        dfs(dep + 1);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        cin >> n;
        for (int i = 1; i <= n; ++i) cin >> p[i];

        found = false;
        dfs(1);

        if (!found) {
            cout << -1 << "\n";
        } else {
            for (int i = 1; i <= n; ++i) cout << ans[i] << " \n"[i == n];
        }
    }
    return 0;
}

复杂度

枚举 $n^n$ 个序列，每个序列求 $p$ 需要 $O(n^3)$ ，总复杂度 $O(n^{n+3})$ ，只能用于 $n \leqslant 8$ 级别的小数据。

瓶颈

暴力完全没有利用 $p$ 的结构信息：它把 $n$ 个位置当成互不相关的自由变量。事实上 $p_i$ 携带的是字符串的 Lyndon 分解 信息，一旦读懂这层信息，每个位置就只剩下很小的选择余地。

正解

关键观察

先回忆两个定义：

若字符串 $u$ 严格小于它的所有真后缀，则称 $u$ 是 Lyndon 串（等价于 $u$ 是其所有循环同构串中严格最小者）。
任意字符串都能唯一分解为若干 Lyndon 串 $B_1+B_2+\cdots+B_k$ ，且满足 $B_1 \geqslant B_2 \geqslant \cdots \geqslant B_k$ ，称为 Lyndon 分解。

由此得到本题的突破口：

$s[x\ldots j]$ 是 $s[1\ldots j]$ 的最小后缀 $\iff$ $x$ 是 $s[1\ldots j]$ 的 Lyndon 分解中最后一段 $B_k$ 的起点。

也就是说， $p_j$ 直接告诉我们：前缀 $s[1\ldots j]$ 的 Lyndon 分解，末尾那一块的起点在哪。于是：

$p_n$ 是整串最后一段 Lyndon 串的起点，记这段为 $[l, n]$ ，则 $l = p_n$ ；
把它切掉， $\;[1, l-1]$ 又是一个前缀，它的最后一段起点是 $p_{l-1}$ ；
反复执行 r = n; l = p[r]; r = l - 1，就能唯一地把整个串切成若干 Lyndon 串。

这一步是后面一切的基础：块与块之间的边界已经完全确定了，我们只需要在每块内部和块与块之间做决定。

思路

第一步：块内复用 Duval 算法。

Duval 算法在扫描一个 Lyndon 串时，只会遇到「 $s_j = s_k$ 」和「 $s_j < s_k$ 」两种情况，绝不会出现 $s_j > s_k$ （一旦出现，当前块就会被拆开，与它是单个 Lyndon 串矛盾）。

在单个块 $[l,r]$ 内维护「近似 Lyndon 串的周期长度」len，以及 Duval 的 $j$ 指针 pre[i] = i - len，则：

条件	含义	记录
$p_i = l$	从 $l$ 到 $i$ 合并成一个新的 Lyndon 串，即 $s_{pre_i} < s_i$	`val[i] = 1`，并令 `len = i-l+1`
$i - p_i = pre_i - p_{pre_i}$	最小后缀整体平移，即 $s_{pre_i} = s_i$	`val[i] = 0`
其它	该前缀的 Lyndon 结构无法由单个块解释	无解

另外块内每个位置都要满足 $p_i \geqslant l$ （最小后缀不能跑到块外），否则无解。

为什么第二条等价于 $s_{pre_i}=s_i$ ？因为若 $s_{pre_i}=s_i$ ，则前缀里「最小后缀起点」的差正好等于平移量，两种信息完全同步；反之两者不同步就说明出现了第三种情况。

第二步：块内最小赋值。

块首 $s_l$ 是唯一的自由变量（Duval 里 $i = l$ 时 $j$ 未定义）。在块内，满足所有关系的最小赋值显然是

s_i = s_{pre_i} + val_i

即「相等就抄过来，严格小于就在抄来的基础上 $+1$ 」。

第三步：块与块之间的约束与贪心。

Lyndon 分解要求 $B_1 \geqslant B_2 \geqslant \cdots \geqslant B_k$ ，也就是每块在字典序上不小于它右边相邻的块。由于右边的块决定字典序时优先级更低，我们从右往左处理每一块，维护右边块的字符数组 nb[1..m]，让当前块在「 $\geqslant$ 右边块」的前提下尽量小。

初始取块首 $s_l = nb_1$ （若无右边块则取最小字符 $0$ ）。设当前位 $i$ ，把 nb 的第 $i-l+1$ 个字符（越界视为 $0$ ）记作 $c$ ：

若 $s_i > c$ ：当前块已经确定比右边块大，后面的位可以随意取最小值，停止调整（记 gt = true）。
若 $s_i < c$ ：还需要补救，分两类——
- val[i] = 1：这一位是自由的，直接把 $s_i$ 抬到 $c$ ，继续往后比较；
- val[i] = 0：这一位必须等于 $s_{pre_i}$ ，不能单独改。只能往前找到最近的 val = 1 位置（记作 now），给 $s_{now}$ 加一，然后从 now+1 重新按公式往后推一遍。由于 now 之前的位都和 nb 相等，加一后必然 $>$ ，于是同样停止调整。
若整块与 nb 逐位相等但长度更短：说明当前块是右边块的前缀，字典序更小，仍需补救。此时把块内最后一个 val = 1 的位置加一，再重算它后面的位。

为什么贪心是对的？ 固定右边块后，块首取值 $x$ 越大，块内每一位的取值都单调不减，即 $f_i(x)$ 关于 $x$ 单调。而所有满足「 $\geqslant$ 右边块」的取值构成一条按 $x$ 排序的链，链上最小的 $x$ 给出该块字典序最小的合法结果。又因为更靠右的块在字典序比较中优先级更低，自右向左逐块取到「不小于右邻块的最小值」等价于优先最小化更靠左的块，因此结果就是全局字典序最小解。同时调整只会向左走、每块内指针单调回退，故总代价是线性的。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-02 15:23
 * update_at: 2026-10-03 12:30
 */
// P9719 [EC Final 2022] Minimum Suffix
// 题意：给每个前缀的最小后缀起点 p_i，还原字典序最小的串 s（字符用正整数表示），无解输出 -1。
// 核心：p_i 就是前缀 i 的 Lyndon 分解中最后一个 Lyndon 串的起点。
//       于是从后往前把整个串切成 Lyndon 串，再在块内模拟 Duval，最后从右往左贪心。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 3000005;

int n;
int p[MAXN];              // 输入的 p_i
int pre[MAXN];            // Duval 中的 j 指针，s[i] 由 s[pre[i]] 推出
unsigned char val[MAXN];  // 1：s[i] = s[pre[i]] + 1（s_j < s_k）；0：s[i] = s[pre[i]]（s_j = s_k）
int s[MAXN];              // 答案串，字符从 0 开始编号
int nb[MAXN];             // 右边相邻 Lyndon 串（next block）的字符

// 手写快读，输入输出可达 3e6 规模
namespace fastio {
const int IBUF = 1 << 22;
char ibuf[IBUF];
int iidx, ilen;

inline int gc() {
    if (iidx == ilen) {
        ilen = (int)fread(ibuf, 1, IBUF, stdin);
        iidx = 0;
        if (ilen <= 0) return -1;
    }
    return (unsigned char)ibuf[iidx++];
}

inline int readInt() {
    int c = gc();
    while (c < '0' || c > '9') {
        if (c == -1) return -1;
        c = gc();
    }
    int x = 0;
    while (c >= '0' && c <= '9') {
        x = x * 10 + (c - '0');
        c = gc();
    }
    return x;
}

const int OBUF = 1 << 22;
char obuf[OBUF];
int oidx;

inline void flushOut() {
    if (oidx) {
        fwrite(obuf, 1, oidx, stdout);
        oidx = 0;
    }
}

inline void putChar(char c) {
    if (oidx == OBUF) flushOut();
    obuf[oidx++] = c;
}

inline void writeInt(int x) {
    if (x == 0) {
        putChar('0');
        return;
    }
    if (x < 0) {
        putChar('-');
        x = -x;
    }
    char tmp[16];
    int t = 0;
    while (x) {
        tmp[t++] = char('0' + x % 10);
        x /= 10;
    }
    while (t) putChar(tmp[--t]);
}
}  // namespace fastio

// 在单个 Lyndon 串 [l, r] 内模拟 Duval 算法。
// 求出每个位置的 j 指针 pre[i] 以及 s_pre 与 s_i 的关系 val[i]。
// 返回 false 表示这个块无法由 p 解释，整组数据无解。
bool prepare_block(int l, int r) {
    val[l] = 1;  // 块首字符是自由变量，val 只作占位

    // 块内每个位置的最小后缀都必须落在块内
    for (int i = l; i <= r; ++i) {
        if (p[i] < l) return false;
    }

    int len = 1;  // 当前近似 Lyndon 串的周期长度
    for (int i = l + 1; i <= r; ++i) {
        pre[i] = i - len;
        if (p[i] == l) {
            // s_j < s_k，从 l 到 i 合并成一个新的 Lyndon 串
            val[i] = 1;
            len = i - l + 1;
        } else if (i - p[i] == (i - len) - p[i - len]) {
            // s_j == s_k，最小后缀起点整体平移 len
            val[i] = 0;
        } else {
            return false;  // 出现第三种情况，无解
        }
    }
    return true;
}

// 构造块 [l, r] 的取值，要求它字典序 >= 右边相邻块 nb[1..m] 且尽量小。
void build_block(int l, int r, int m) {
    int len = r - l + 1;
    int gt = 0;  // 当前块是否已经确定大于右边块
    s[l] = (m >= 1) ? nb[1] : 0;

    for (int i = l + 1; i <= r; ++i) {
        s[i] = s[pre[i]] + val[i];
        int t = i - l + 1;
        int c = (t <= m) ? nb[t] : 0;  // 右边块第 t 个字符，越界视为最小字符 0
        if (s[i] > c) {
            gt = 1;
        }
        if (!gt && s[i] < c) {
            if (val[i]) {
                // 这一位自由，直接抬到与右边块相等
                s[i] = c;
            } else {
                // 这一位必须等于 s[pre[i]]，只能把前面最近的自由位加一
                int now = i;
                while (val[now] != 1) --now;
                i = now;  // 从 now 之后重新推一遍
                s[now]++;
                gt = 1;
            }
        }
    }

    if (!gt && len < m) {
        // 整块是右边块的前缀，字典序更小，抬高最后一个自由位
        int now = r;
        while (val[now] != 1) --now;
        s[now]++;
        for (int i = now + 1; i <= r; ++i) s[i] = s[pre[i]] + val[i];
    }
}

// 处理一组数据，返回是否存在解
bool solve_case() {
    n = fastio::readInt();
    for (int i = 1; i <= n; ++i) p[i] = fastio::readInt();

    // 从后往前切分 Lyndon 串：block = [l, r]，其中 l = p[r]
    int r = n;
    int m = 0;  // 右边相邻块的串长
    while (r >= 1) {
        int l = p[r];
        if (!prepare_block(l, r)) return false;

        build_block(l, r, m);

        // 当前块成为下一轮的“右边块”
        m = r - l + 1;
        for (int i = l; i <= r; ++i) nb[i - l + 1] = s[i];
        r = l - 1;
    }
    return true;
}

int main() {
    int T = fastio::readInt();
    while (T--) {
        if (!solve_case()) {
            fastio::putChar('-');
            fastio::putChar('1');
            fastio::putChar('\n');
        } else {
            for (int i = 1; i <= n; ++i) {
                fastio::writeInt(s[i] + 1);
                fastio::putChar(i == n ? '\n' : ' ');
            }
        }
    }
    fastio::flushOut();
    return 0;
}

复杂度

每个块内 Duval 模拟、构造、以及向左寻找 val = 1 的调整都是线性的（块内指针只单调左移，均摊 $O(1)$ ），切块也是线性。故总时间复杂度 $O\!\left(\sum n\right)$ ，空间复杂度 $O(n)$ 。配合手写快读快写即可通过 $\sum n \leqslant 3\times 10^6$ 的数据。

样例推演

以 1 2 2 为例（样例第 5 组）。先切块： $l=p_3=2$ ，得到右边块 $[2,3]$ ；再 $r=1,\ l=p_1=1$ ，得到左边块 $[1,1]$ 。

从右往左：右边块 $[2,3]$ 无右邻，取 $s_2=0$ ； $i=3$ 时 val[3]=1（因为 $p_3=2=l$ ），故 $s_3=s_2+1=1$ ，输出块 0 1。

再处理左边块 $[1,1]$ ：块首取右邻首字符 $s_1 = nb_1 = 0$ 。此时 gt = false，且块长 $1 < 2 = m$ ，说明 0 是 0 1 的前缀、偏小，于是把块内最后一个 val = 1 的位置（就是 $1$ ）加一， $s_1 = 1$ 。

最终 $s = 1,0,1$ ，加一还原为 2 1 2，与样例一致。

总结

本题的关键是把「最小后缀起点」翻译成「Lyndon 分解末块起点」，从而把 $p$ 变成整串的 Lyndon 结构：

用 r = n, l = p[r] 迭代切出所有 Lyndon 块；
块内用 $p_i = l$ 与 $i-p_i = pre_i - p_{pre_i}$ 判定 val 并模拟 Duval，顺便判无解；
自右向左贪心，块内按 $s_i = s_{pre_i} + val_i$ 取最小，遇到「小于右邻块」时把最近的 val = 1 位置加一，即可在 $O(n)$ 内得到字典序最小解。

难点不在复杂度，而在于能否看懂 $p$ 与 Lyndon 分解之间的对应关系，以及块间比较时「只加最近一个自由位」这一调整细节。