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

qianyuzhe · 2026-03-08 17:07:37 · 题解

AFO 了。

注意到 \operatorname{mex}\{a_l,\dots,a_r\}=\min\{a_1,\dots,a_{l-1},a_{r+1},a_n\}。

也就是说，\operatorname{mex} 只与前后缀 \min 有关，再次运用上述性质，不难用 2n 次操作求出所有前后缀 \min。

考虑优化，注意到前后缀 \min 单调，达到 0 后就不再变化，利用这点可以优化至 n 次。

然后考虑还原出一种合法的排列，对于每一段未确定的数，记录一下它们必须大于几，把所有限制排序后从大到小填即可。

代码不放了。