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

· · 题解

赛时思路。

考虑 0 \sim n-1 顺次找，维护支配值域前缀的区间 [l,r]，如果在两边的话可以直接二分，在中间的话随便填一个空位就行。

注意到我们询问 $[l,r]$ 时，询问答案为 $x$，设此时填的 $i$ 有 $i < x$，则 $i \sim x - 1$ 的所有数都能不询问直接填到中间，因此除去 $i$ 和当前支配区间 $[l,r]$ 相邻的情况外，其余情况次数一定是不劣的。 $3n$ 次，记忆化一下即可 $1.5n + \log n$ 次。 ~~考虑优化，发现我们给支配区间同时扩展 $1$ 时信息量更大，于是先问中间再问两边，随一下期望询问次数 $1.25n$ 次，没有卵用。~~ 发现上面的一个瓶颈在于找 $0$，于是我们考虑依次询问 $[1,n-1],[2,n-1],[3,n-1] \dots$ 这些区间，直到找到第一个 $0$ 为止，显然在找 $0$ 的过程中我们也能知道所有前缀 $\min$ 的数的值，其他数不知道，不过容易发现不知道的数都可以按照前面的做法放到中间的位置，写了一下，询问次数为 $n + 1$ 次。 发现多一次的原因在于询问了 $[0,n-1]$ 这个区间，特判掉即可。