---

1. 问题分析

我们有一个字符串 $a$，长度为 $n$。
定义 $s_i$ 为删除位置 $i$ 的字符后得到的字符串。
我们要按字典序对 $s_1, s_2, \dots, s_n$ 排序，如果两个字符串相同，则位置编号小的排在前面。
最后输出排序后的位置编号序列。

---

2. 直接模拟的复杂度

如果直接构造 $s_i$ 再排序，每个 $s_i$ 长度 $n-1$，构造总 $O(n^2)$，再排序 $O(n^2 \log n)$，显然不可行。

---

3. 关键观察

比较 $s_i$ 和 $s_j$（假设 $i < j$）：

• 当 $i < j$ 时，$s_i$ 与 $s_j$ 的前 $i-1$ 个字符相同（都是 $a[1..i-1]$）。
• 第 $i$ 个字符：
  • 在 $s_i$ 中，第 $i$ 个字符是原串的 $a_{i+1}$（因为 $a_i$ 被删了）。
  • 在 $s_j$ 中，第 $i$ 个字符是原串的 $a_i$（因为 $j > i$，所以 $a_i$ 还在）。
• 因此，比较 $s_i$ 和 $s_j$ 时，在位置 $i$ 处比较的是 $a_{i+1}$（来自 $s_i$）和 $a_i$（来自 $s_j$）。

更一般地，对于 $i < j$：

• 对于 $k < i$：$s_i[k] = a_k = s_j[k]$。
• 对于 $k = i$：$s_i[k] = a_{i+1}$，$s_j[k] = a_i$。
• 对于 $k > i$ 且 $k < j$：$s_i[k] = a_{k+1}$，$s_j[k] = a_k$。
• 对于 $k = j$：$s_i[k] = a_{j+1}$，$s_j[k] = a_{j+1}$（因为 $s_j$ 删掉 $a_j$ 后，这个位置是 $a_{j+1}$，而 $s_i$ 中 $j$ 位置也是 $a_{j+1}$）。
• 对于 $k > j$：$s_i[k] = a_{k+1}$，$s_j[k] = a_{k+1}$。

所以实际上，比较 $s_i$ 和 $s_j$ 时，第一个不同的位置是 $\min(i,j)$ 吗？
不对，因为 $i<j$ 时，第一个不同位置是 $i$，比较的是 $(a_{i+1}, a_i)$。

---

4. 更简单的比较方法

$s_i$ 相当于原字符串去掉第 $i$ 个字符。
比较 $s_i$ 和 $s_j$ 时，可以这样看：

• 它们的前 $i-1$ 个字符相同。
• 在第 $i$ 个字符：
  • $s_i$ 的第 $i$ 个字符 = $a_{i+1}$
  • $s_j$ 的第 $i$ 个字符 = $a_i$
• 如果 $a_{i+1} \neq a_i$，则可以直接分出大小。
• 如果相等，则继续比较后面的字符，但注意 $s_i$ 和 $s_j$ 在 $i+1$ 到 $j-1$ 段，$s_i$ 取 $a_{i+2..j}$，$s_j$ 取 $a_{i+1..j-1}$，这其实相当于比较原串从 $i+1$ 开始的后缀和从 $i+2$ 开始的后缀（当 $j > i+1$ 时）。

更简单的办法：
$s_i$ 可以看作原串 $a$ 在位置 $i$ 跳过，所以：

$$s_i = a[1:i-1] + a[i+1:n]$$

比较 $s_i$ 和 $s_j$ 时，可以按顺序比较字符，遇到位置 $i$ 时跳过，遇到位置 $j$ 时跳过。
但这样比较仍然是 $O(n)$ 的，总排序 $O(n^2 \log n)$ 不行。

---

5. 高效比较方法

我们注意到，对于 $i < j$，比较 $s_i$ 和 $s_j$ 等价于比较两个字符串：

• $X = a_1 a_2 \dots a_{i-1} a_{i+1} a_{i+2} \dots a_n$
• $Y = a_1 a_2 \dots a_{i-1} a_i a_{i+1} \dots a_{j-1} a_{j+1} \dots a_n$

它们的前 $i-1$ 个字符相同，第 $i$ 个字符分别是 $a_{i+1}$ 和 $a_i$。

所以：

• 如果 $a_i < a_{i+1}$，那么 $s_j < s_i$（因为 $Y$ 在第 $i$ 个字符 $a_i$ 小于 $X$ 的 $a_{i+1}$）。
• 如果 $a_i > a_{i+1}$，那么 $s_i < s_j$。
• 如果 $a_i = a_{i+1}$，则继续比较后面的字符，但后面的字符相当于比较 $s_{i+1}$ 和 $s_j$（因为 $s_i$ 从 $i+1$ 开始和 $s_{i+1}$ 从 $i+1$ 开始只差一个字符的偏移）。

实际上，当 $a_i = a_{i+1}$ 时，$s_i$ 和 $s_j$ 的比较等价于比较原串中从 $i+2$ 开始的后缀和从 $j+1$ 开始的后缀（如果 $j > i+1$），但这样递归比较复杂。

---

6. 已知技巧：相邻字符比较法

有一个已知结论（类似 Codeforces 875B 或一些后缀排序题）：
对于 $i < j$，$s_i$ 与 $s_j$ 的大小关系由第一个 $a_k \neq a_{k+1}$ 的位置 $k \ge i$ 决定，具体来说：

• 如果 $a_i < a_{i+1}$，那么 $s_{i+1} < s_i$，并且 $s_i$ 在 $s_{i+1}$ 之后。
• 如果 $a_i > a_{i+1}$，那么 $s_i < s_{i+1}$。
• 如果 $a_i = a_{i+1}$，则比较关系与更后面的第一个不同字符有关，但可以证明：
  设 $p$ 是满足 $a_p \neq a_{p+1}$ 的最小位置 $p \ge i$，如果 $a_p < a_{p+1}$，则 $s_i > s_{i+1}$，否则 $s_i < s_{i+1}$。

更简单的做法：
比较 $s_i$ 和 $s_j$ 时，第一个不同的位置是 $\min(i,j)$ 吗？不，是 $\min(i,j)$ 吗？我们仔细推导：

对于 $i < j$：

• 前 $i-1$ 个字符相同。
• 第 $i$ 个字符：$s_i$ 是 $a_{i+1}$，$s_j$ 是 $a_i$。
• 所以比较 $(a_{i+1}, a_i)$ 即可决定顺序。

因此：
$s_i < s_j$ 当且仅当 $a_{i+1} < a_i$，对于 $i < j$
$s_i > s_j$ 当且仅当 $a_{i+1} > a_i$
如果 $a_{i+1} = a_i$，则 $s_i = s_j$ 吗？不是，还要继续比较，但继续比较时，$s_i$ 从 $i+1$ 开始相当于 $s_{i+1}$ 从 $i+1$ 开始，所以可以递归。

---

7. 最终简单结论（来自已知解法）

有一个经典做法：
定义 $type_i$：

• 如果 $a_i < a_{i+1}$，则 $s_i$ 在排序中应该排在 后面（因为删除 $i$ 后下一个字符更大，字符串变大）。
• 如果 $a_i > a_{i+1}$，则 $s_i$ 在排序中应该排在 前面。
• 如果 $a_i = a_{i+1}$，则 $type_i$ 与 $type_{i+1}$ 相同。

这样我们可以 $O(n)$ 预处理出每个 $i$ 的“类型”，然后按照类型排序：
类型 0（$a_i > a_{i+1}$ 或 相等但后续第一个不同是大于）的排在类型 1 前面。
同类型的 $i$ 按原顺序排列（因为相等时编号小的优先）。

---

8. 算法步骤

1. 从后往前处理，设 $type[n] = 0$（因为 $a_{n+1}$ 视为最小）。
2. 对于 $i$ 从 $n-1$ 到 1：
   • 如果 $a_i < a_{i+1}$，则 $type[i] = 1$（$s_i$ 大）
   • 如果 $a_i > a_{i+1}$，则 $type[i] = 0$（$s_i$ 小）
   • 如果 $a_i = a_{i+1}$，则 $type[i] = type[i+1]$
3. 将 $1..n$ 按 $type[i]$ 分组，$type=0$ 的在前，$type=1$ 的在后。
4. 在每组内，$type=0$ 的按 $i$ 升序排列（因为对于 $type=0$，$i$ 越小字符串越小），$type=1$ 的按 $i$ 降序排列（因为对于 $type=1$，$i$ 越小字符串越大，所以大的 $i$ 放前面）。

---

9. 样例验证

输入：

7
aabaaab

$a$ = a a b a a a b
比较相邻：

• i=1: a=a → type=type[2]
• i=2: a<b → type=0
• i=3: b>a → type=0
• i=4: a=a → type=type[5]
• i=5: a=a → type=type[6]
• i=6: a<b → type=0
• i=7: 默认 0

从后往前：

• type[7]=0
• type[6]: a<b → 0
• type[5]: a=a → type[6]=0
• type[4]: a=a → type[5]=0
• type[3]: b>a → 0
• type[2]: a<b → 0
• type[1]: a=a → type[2]=0

所以所有 type=0。
type=0 组内按 i 升序：1 2 3 4 5 6 7？
但样例输出是 3 7 4 5 6 1 2，说明我们还需要进一步区分。

---

10. 更精确的已知解法

实际上这类题的标准解法是：

• 比较 $s_i$ 和 $s_j$ 时，相当于比较原串从 $i+1$ 开始的后缀和从 $j+1$ 开始的后缀（当 $i<j$ 且 $a_i=a_j$ 时继续）。
• 因此，可以先求出原串的后缀数组 SA 和 rank。
• 然后 $s_i$ 与 $s_j$ 的比较：
  • 如果 $a_i \neq a_j$，直接比较 $a_i$ 和 $a_j$。
  • 如果 $a_i = a_j$，则比较 $rank[i+1]$ 和 $rank[j+1]$。

但这里 $i$ 和 $j$ 是删除的位置，所以对于 $i<j$：

• 如果 $a_i \neq a_{i+1}$，直接得出结果。
• 如果 $a_i = a_{i+1}$，则比较 $s_i$ 和 $s_j$ 等价于比较后缀 $i+2$ 和后缀 $j+1$。

因此，我们可以 $O(n)$ 预处理，或者直接使用后缀数组 $O(n \log n)$ 排序。

---

11. 实现方案（后缀数组法）

1. 构建字符串 $a$ 的后缀数组 SA 和 rank 数组。
2. 定义比较函数 $cmp(i, j)$：
   • 如果 $a_i < a_j$，则 $s_i < s_j$。
   • 如果 $a_i > a_j$，则 $s_i > s_j$。
   • 如果 $a_i = a_j$，则比较 $rank[i+1]$ 和 $rank[j+1]$（如果 $i=n$，则 $rank[n+1]=-1$，最小；同理 $j=n$ 类似）。
3. 用这个比较函数对 $1..n$ 排序。

复杂度 $O(n \log n)$，可过 $n=10^6$。

---

12. 代码框架（C++）

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e6 + 5;

int n;
char a[MAXN];
int rk[MAXN], sa[MAXN], tmp[MAXN], k;

bool cmp_sa(int i, int j) {
    if (rk[i] != rk[j]) return rk[i] < rk[j];
    int ri = i + k <= n ? rk[i + k] : -1;
    int rj = j + k <= n ? rk[j + k] : -1;
    return ri < rj;
}

void build_sa() {
    for (int i = 1; i <= n; i++) {
        sa[i] = i;
        rk[i] = a[i];
    }
    for (k = 1; k <= n; k *= 2) {
        sort(sa + 1, sa + n + 1, cmp_sa);
        tmp[sa[1]] = 1;
        for (int i = 2; i <= n; i++) {
            tmp[sa[i]] = tmp[sa[i - 1]] + (cmp_sa(sa[i - 1], sa[i]) ? 1 : 0);
        }
        for (int i = 1; i <= n; i++) rk[i] = tmp[i];
    }
}

int rank_[MAXN];

bool cmp_i(int x, int y) {
    // 比较 s_x 和 s_y
    if (a[x] != a[y]) return a[x] < a[y];
    if (x == n) return true;   // s_x 已结束
    if (y == n) return false;
    return rank_[x + 1] < rank_[y + 1];
}

int main() {
    scanf("%d", &n);
    scanf("%s", a + 1);
    build_sa();
    for (int i = 1; i <= n; i++) rank_[sa[i]] = i;
    vector<int> idx(n);
    iota(idx.begin(), idx.end(), 1);
    sort(idx.begin(), idx.end(), cmp_i);
    for (int i = 0; i < n; i++) printf("%d ", idx[i]);
    puts("");
    return 0;
}

---

13. 总结

这道题的核心在于理解删除一个字符后的字符串比较可以转化为对原串后缀的比较，从而利用后缀数组快速排序。