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

· · 题解

我身边有个天天出 \text{mex} 题的人，怎么回事呢？

题意

让你猜一个 0\sim n-1 的排列，每次可以询问区间 \text{mex}，要求在至多 n 次询问下求出一个合法排列。

思路

以下为方便默认下标为 1\sim n。称这个排列为 p。

注意到 \text{mex} = 补集 \min。也就是说求一个区间 \text{mex} 相当于求整个排列扣掉这个区间后一段前缀一段后缀的 \min。

显然你不希望得到前后缀拼起来的信息，那你还不如分开求。假设我们求好了每个前后缀的 \min 各花费 n 次，分别记作 pre_i=\min\limits_{j=1}^i p_j,suf_i=\min\limits_{j=i}^n p_j，如何构造出一个合法排列？

注意到有些位置的值是可以直接求得的。若对于某个 i，pre_i\not=pre_{i-1} 则说明一定是 p_i 造成的贡献，我们就有 p_i=pre_i。suf_i\not=suf_{i+1} 同理。

剩下的位置，要填的数的限制都仅仅是 p_i\ge\max\{ pre_i,suf_i\}。我们按照值从大往小塞数，把没选过的大的数尽量往限制更强（也就是 \max\{ pre_i,suf_i\} 更大）的地方贪心塞。可以证明这样一定不劣。

但是我们所要求的次数是 n 而不是 2n。我们再找一些性质。

通过特殊性质 B 又注意到：对于全局 \min（也就是 0）所在位置，其左半边的 suf 一定全是 0，右半边的 pre 一定全是 0。

这下我们就砍掉左半边的 suf 和右半边的 pre 不用问了，总询问次数 n。

那么又如何找 0 的位置呢？很简单，我们从左往右询问 pre，找到一个 pre_{i_0}=0 就说明 p_{i_0} 要填 0 了。

时间复杂度 O(n\log n)。瓶颈在于后面的填数，当然你要不嫌麻烦开桶存位置也行。

代码

出了再放吧。