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

Jasonbenji · 2026-03-08 15:52:08 · 题解

两个排列等价相当于对于每个 0\leq i<n，都有包含 [0,i] 所有数的极小区间相同。

于是考虑：先求出 p_0=\operatorname{query}(1,n-1) 和 p_{n-1}=\operatorname{query}(0,n-2)，然后考虑贴着两边往里扩展。

假设当前已经确定了 p_0,p_1,...,p_l 和 p_r,p_{r+1},...,p_{n-1}，其中 p_l 和 p_r 是确定具体值的，考虑如何计算确定其他内容。不失一般性，我们假设 p_l>p_r，于是尝试去确定一下 p_{l+1}。由于之前得到了 p_l 的具体值，所以一定有 \operatorname{query}(l+1,n-1)=p_l，因此我们可以询问 \operatorname{query}(l+2,n-1)=tmp，若 tmp=p_l，则说明 p_{l+1}>p_l，标记上并继续扩展，用相同的方式得到 p_{l+1},p_{l+2},...,p_{to-1}>p_l，直到能够确定 p_{to}=\operatorname{query}(to+1,n-1)<p_l，就 l:=to 继续去做。

最后把标记大于几的值随便填上就好了。

下面要说明为什么确定到“p_{to}>p_l”就可以了，并且不会有更多的信息：由于 p_{to}>p_l>p_r，和 p_{to} 有关的极短区间必然会包含 [l,r]，则 p_{to} 的值只需 >p_l 即可，其余无论如何不影响正确性。

显然每多确定一个位置只需要一次操作因此总共 n 次。