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

zzy0618 · 2026-03-08 15:09:50 · 题解

可以想出一个很直接的 2n+\log n 的做法，先倍增出 0 的位置 p，然后依次考虑 i=1,2,\dots,n-1 的位置，并维护一个包含目前所有数的极小的区间 [l,r]，先用一次 [0,r] 查询判断 i 相对于 [l,r] 的方向，然后暴力拓展 [l,r] 为 [l-1,r] 或 [l,r+1]，直至 \text{mex} 发生变化。假设新区间 [l,r] 的 \text{mex} 变化至 j，就将 i 放在区间边缘，(i,j) 内的数随便往区间里空的位置扔就行，最后令 i\gets j。区间是不减的，总计询问 n 次，并且最劣情况下需要判断 n 次方向。

重要的发现是，假设 i 在区间 [l,r] 左边，查询 [l-1,r] 与查询 [l-1,n-1] 对于判断 i 是否在区间中是等效的，在右边同理。对于一个 i，查询 [0,r] 和 [l,n-1] 判断在当前 [l,r] 的左中右，如果不在 [l,r] 内就拓展区间。这样只需要对前后缀进行查询，并且有效总数为 n+1 个，总查询次数 n+1+\log n。