CF1764G2 Doremy’s Perfect DS Class (Medium Version) 题解

前言

前置芝士：CF1764G1 的解法。

考虑在 G1 的基础上进行一个小小的优化。

G1 的最大询问次数是 $3\log n$ ，其瓶颈在于当 $n$ 为偶数时，我们需要预先额外花费 $\log n$ 的时间去找到 $n$ 的位置，从而消除后续询问里 $n$ 的影响，因为这时 $n$ 与 $1$ 一样都具有除以 $2$ 向下取整的结果唯一的性质。

而 G2 把最大询问次数限制到了 $25$ 次，所以我们需要找一种更高效的辨别 $n$ 和 $1$ 的方式来代替预先询问。

当我们对 $[1,k]$ 和 $[k+1,n]$ 两个区间进行询问时，除了 $1$ 和 $n$ 之外，两个区间里无法配对数字的数量一定是相等的，那我们可以分类讨论 $1$ 和 $n$ 的位置：

当 $1$ 和 $n$ 在同一个区间里时，这个区间里未配对的数字个数会比另一边大 $2$ ，于是继续处理这个区间就好。
当 $1$ 和 $n$ 分居在两个区间里时，两个区间里未配对的数字个数相等，我们只需要对其中一个区间进行一次 $?\ l\ r\ n$ 的询问，如果得到的结果是 $2$ 那就证明 $1$ 不在这个区间里，反之则证明 $1$ 在另一个区间里，于是我们就可以记录下 $n$ 所在区间，继续对有 $1$ 的区间进行询问。