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

· · 题解

乱做。

就直接先搞出 0 的位置来，然后考虑 1 的位置是在左边还是在右边，然后取得 1 的位置以后可能 2\sim p 的数在中间啥的，我们就继续考虑 p+1 的位置……

你跟我说 2\sim p 这一段怎么放，随便放就行，因为这里的对 MEX 是不影响的，放在 0,1 位置的中间即可。

然后这样做最优秀的查询次数可以到 \frac{3}{2}n + \log n。

我们换个思路重新看。

还是找到 0 的位置。然后考虑到 MEX 就是补集 \min，发现 \operatorname{query}(l,r) 就是前缀 [0,l-1] 的 \min 与后缀 [r+1,n-1] 的 \min。这个直接把一个前缀或者后缀变成空的，然后另一边从 0 所在位置扫过去。

二分 0 可以做到 \log n + n，差不多有 80 了。

然后又会发现这里的 0 的位置也可以直接看作前缀清空以后后缀从后面扫回来。直接就发现了 0 的位置，这里的查询还能重复利用。做到 n+1 次查询（记得重复利用）。

最后我们会发现我们查询了 (0,n-1)，这个答案太弱智了就是 n，省掉了这一次就满分了。