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

a_foolish_OIer · 2026-03-08 15:14:04 · 题解

感觉更适合 D1T1，好像和大家的做法不太一样。

首先 \operatorname{mex} 根据定义转化成补集 \min，也就是 \operatorname{mex}(l,r)=\min(\min(1,l-1),\min(r+1,n))。

只要求所有 \operatorname{mex} 相等，根据转化，我们只需要让前后缀 \min 相等即可，我们先用 2n 次查询出 p 的前后缀 \min，对于前后缀 \min 产生改变的地方，就把这个值填上去。

对于剩下的，为了不干扰前后缀 \min，考虑贪心策略，对于要求 \min 越大的位置匹配越大的数，这肯定能产生一组解。

然后你发现若前后缀 \min 出现了 0 就不用继续询问了，剩下的肯定都是 0，然后就把 2n 次变成了 n 次。

然后就做完了。