题解：P15652 [省选联考 2026] 排列游戏 / perm

xiao7_Mr_10_ · 2026-03-08 16:27:03 · 题解

愤怒了，这种题做了我 3h。

我们考虑经典 trick：查排列 p 的一段区间 [l,r] 中的 mex 实际上是 \min(f_{l-1},g_{r+1})。其中 f,g 数组分别为 p 的前缀、后缀最小值，令 f_0=g_{n+1}=10^{18}。

然后发现原序列被判定为合法的充要条件实际上就是原排列 p 的前后缀最小值数组和构造出来的排列的 f,g 相等。

充分性很显然，必要性考虑 f_i = x，但是有一组解 f_i = y，查询区间 [i+1,n] 的最大值就出问题了，至于边界，那是固定的。所以必要性也有，这就是一组充要条件。

然后我们只需要问 n 次确定一下前后缀最小值数组 f,g，这一点可以用 0 作为分界点，这样总体只问了 n 次。然后在排列中确定每个最小值的位置，剩下没确定的位置需要满足 p_i \ge \ max(f_i,g_i)，考虑贪心填满足条件最小的，因为可以看做 p_i \ge h_i，其中 h_i = \max(f_i,g_i) 这个 h 显然是单调不降的，在 i 位置放一个大一点的数后面没办法放较小的数了。

时间复杂度 O(n \log n)，找第一个比 \max(f_i,g_i) 大的用 set 容器，当然可能可以精细实现到 O(n)。