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

· · 题解

首先考虑 n^2 次询问怎么做，此时我们可以随便询问每一组 (l,r)。我们从小到大确定每个数的位置。

首先考虑确定 0。只需要对每一个数单独 query，看 \text{mex} 是否为 1 即可。然后考虑已知 0\sim i-1 的位置 v_0\sim v_{i-1}，维护最小的包含它们的区间 [l,r]，如果这一段的 \text{mex} 值比 i 大，i 可以在 [l,r] 中任何一个没有被确定的位置上。随便找一个空位填上就可以。否则我们假设 v_i 在这个区间右边，显然 r 增大之后 \text{query}(l,r) 的值单调不降。必然存在某一个 r 右边的位置 r' 使得 \text{query}(l,r'-1)=i-1 且 \text{query}(l,r')\geq i，此时可以确定 v_i=r'。暴力地寻找 r' 即可做到 n^2 次询问。如果 v_i 在区间左边也是同理的。

然后如果把暴力找改成二分查找 r'，就可以做到 n\log n 次询问（可能略大一点）。

接下来观察性质。对于一次询问 \text{query}(l,r)，由于这是一个排列，如果 r\neq n-1，[l,r] 的 \text{mex} 实际上就是 [r+1,n-1]\cup[0,l-1] 区间的 \min。于是对于每组询问 \text{query}(l,r)，都可以拆成 \min(\text{query}(0,r),\text{query}(l,n-1))。我们预处理询问 \text{query}(0,i) 和 \text{query}(i,n-1) 就可以做到 2n 次询问。

然后我场上做到这不会了，请输入文本。

根据上面的分析，\text{query}(0,i) 肯定单调不降，\text{query}(i,n-1) 一定单调不增。并且对于 i<v_0，有 \text{query}(0,i)=0；对于 i>v_0，有 \text{query}(i,n-1)=0。

于是我们只需要询问 n+1 次了。去掉 \text{query}(0,n-1)=n，只需要询问 n 次，可以通过本题。