本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-09-28 07:38:41

做 AGC001F 的时候想的，结果越想越乱，总结一下。

• 逆排列：对 $p$ 来说满足 $q_{p_i}=i$ 且 $p_{q_i}=i$ 的排列 $q$。事实上两个条件等价，都是值与下标互换。
• 引理：最小化 $p$ 的字典序，相当于最大化其逆排列 $q$ 的逆序字典序。

考虑 $p$ 字典序最小在 $q$ 上是什么，发现要让 $1$ 尽可能靠前，再让 $2$ 尽可能靠前，以此类推。因此倒着进行这个过程，直到只能填 $1$ 时才填 $1$，否则在只能填 $2$ 时填 $2$，这对应其字典序最大。

有以下三个问题：

• 要求排列中 $i$ 在 $j$ 之前出现，求字典序最小的排列 $p$。

相当于字典序最小的拓扑序，因此直接由 $i$ 向 $j$ 连边，每次取入度为零的最小值放在 $p$ 开头即可。

• 要求 $p_i<p_j$，求字典序最小的排列 $p$。

比较自然的想法是 $i$ 向 $j$ 连边，之后每次取最小编号并赋值。然而这是错的，容易用 $n=3,(3,1)$ 直接卡掉。

这是因为该过程并没有尽可能最小化 $p_1$，而是最小化了 $p$ 的逆排列 $q$ 的字典序。然而根据引理，实际上要做的是最大化 $q$ 的逆序字典序。

该限制转化到 $q$ 上为 $i$ 在 $j$ 之前出现，求逆序字典序最大的排列 $q$，根据上一题这需要由 $j$ 向 $i$ 连边，并倒着确定每个 $q$ 的取值，之后再转化回原排列 $p$。

然后发现这次的拓扑排序部分与上题相比取了个逆，这与 $q$ 转化回 $p$ 的取逆抵消了。因此本题可以直接由 $j$ 向 $i$ 连边，每次取最大编号并赋值， 这与上一段中的做法等价。

• 要求排列中 $i$ 在 $j$ 之前出现，之后要求先让 $1$ 尽可能靠前，在此前提下让 $2$ 尽可能靠前，以此类推。

再次考虑逆排列 $q$，发现这其实就是 $q_i\lt q_j$，求字典序最小的排列 $q$，只需要对上题的结果取逆排列即可得到答案，这可以直接在拓扑排序部分修改。本题有原题 HDU4857。