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

· · 题解

这是考场思路。

我们首先可以考虑一个性质。

如果有以下这种情况。

i 0 1 2 3 4
a_i 1 ? 0 ? 2

那么我们就会发现这两个空的位置随机填数是没问题的。

然后发现这个东西可以直接做完 A 性质，感觉有点对。

接着往下思考。

发现我们可以通过一次询问确定边上的数，即询问 \left[0,n-2\right] 区间这种。

又发现 B 性质利好这一做法。那大概率想对了。做法即问 \left[0,n-2\right]、\left[0,n-3\right] 这样。另一边同理。

那考虑不单调情况怎么做。

结合最上面的性质。

以右边为例。在从右边缩小区间的过程中，若当前区间的 \operatorname{mex} 较之前小，那么可以确定当前的数。若当前数 \operatorname{mex} 较之前无变化，那么需要填一个比区间 \operatorname{mex} 大至少 2 的数。

做法就是先填确定的数，再填大数即可。

从左边和右边各自跑到 0 处，次数为 n。

代码只需要模拟上面的过程即可。