P14490 [集训队互测 2018] 小修和小栋猜数字 题解

可以发现若 $n\neq 1$，则可确定数字数量的上界是 $\max(0,n-4)$。下面考虑证明这一点：

• 若 $n<3$，则显然无法询问出任何有效信息。
• 若 $n=3$，则显然询问出全局中位数无法确定任何一个位置的值。
• 若 $n>3$，则考虑 $a$ 序列中最小的两个数，设其分别位于 $p,q$ 位置，则考虑交换这两个位置的值得到新的序列 $a'$，可以证明此时无论如何询问中位数，都无法区分这两个序列。记除了 $p,q$ 之一外，询问的两个位置为 $i,j$（$i<j$），则此时必有 $a_i>a_j>\max(a_p,a_q)$，因此询问中位数得到的值必然不是 $a_p$ 或者 $a_q$ 中的一个，而 $a_i=a'_i,a_j=a'_j$，因此无法区分。
• 同样的，$a$ 序列的最大的两个数交换后也是无法区分的。因此可以确定的数的上界被缩小到 $\max(0,n-4)=n-4$。后面将考虑如何交互取到这个上界：
  • 考虑把元素一个一个加入。具体的，先询问前四个元素，将这四个元素的全部选三个元素的 $4$ 种组合方案都询问一遍，得出前四个元素的次小值 $mi'$ 次大值 $mx'$ 以及最小的两个位置 $l_0,l_1$ 最大的两个位置 $r_0,r_1$，但是无法区分 $l_0,l_1$ 和 $r_0,r_1$ 哪个是最小（大）值哪个是次小（大）值。
  • 具体来说，记四个数分别是 $b_0,b_1,b_2,b_3$，询问信息为 $c_i$ 是 $b$ 中除了 $b_i$ 以外询问的另外三个数的中位数的值，则 $b_0,b_1,b_2,b_3$ 中必然是两个值为次大值两个值为次小值。显然此时两个次大值对应就是 $l_0,l_1$，两个次小值对应就是 $r_0,r_1$。当然这里是无法区分 $l_0,l_1$ 和 $r_0,r_1$ 的。
  • 此时可以发现询问了 $b_0,b_1,b_2$ 后 $b_3$ 的值可以直接通过 $b_0,b_1,b_2$ 推出来，因此可以再省略一次询问，用 $3$ 次询问确定前 $4$ 个数之间的部分关系。
  • 然后考虑加入一个新的位置 $i$。先询问 $l_0,r_0,i$ 三个位置，记询问得到的中位数值为 $val$。则考虑对 $val$ 和 $mi',mx',i$ 的大小和相等关系进行分类讨论：
    • 若 $mi'<val<mx'$，则此时必有 $val=a_i$，无需更新 $l_0,l_1,r_0,r_1,mi',mx'$ 的信息。
    • 若 $val=mx'$，则此时因为值互不相同所以必有 $a_i\neq val$。因此只能是 $a_{r_0}=val$，然后更新新的 $r_0$ 候选为 $i$，新的次大值就是 $\min(a_{r_1},a_i)$。考虑怎么询问出新的次大值，容易想到再询问一次 $l_0,r_1,i$ 这三个位置，因为 $a_{l_0}<a_{r_1}\land a_{l_0}<a_i$，因此三个数排序一定形如 $a_{l_0}<\min(a_{r_1},a_i)<\max(a_{r_1},a_i)$，三个数的中位数恰为 $\min(a_{r_1},a_i)$。
    • 若 $val>mx'$，则可以确定 $r_0$ 必然是加入 $i$ 前数组的最大值，$r_1$ 必然是加入 $i$ 前数组的次大值。因此可以直接确定 $a_{r_1}=mx'$，$val=\min(a_i,a_{r_0})$ 就必然是加入 $i$ 后数组的新次大值。因此直接更新 $r_1\leftarrow i,mx'\leftarrow val$ 即可。
    • 剩下 $val<mi'$ 和 $val=mi'$ 两种情况，这两类和 $val>mx',val=mx'$ 的情况是对称的，这里就不再赘述了。

然后再考虑分析询问次数。容易发现询问次数最多肯定是每次加一个 $i$ 时都取到 $val=mi'$ 或 $val=mx'$，最坏询问次数为 $2n-5$。至于标程运行了多少次我哪知道，反正能过就是了，也不知道当时集训队选手是通过什么手段搞到标程询问次数的。

:::success[Code]

void guess(int n) {
    if (n < 5) return;
    int b0 = ask(1, 2, 3), b1 = ask(1, 2, 4), b2 = ask(1, 3, 4);
    int l0, l1, r0, r1, mip, mxp;
    if (b0 == b1) l0 = 1, l1 = 2, r0 = 3, r1 = 4, mip = b0, mxp = b2;
    else if (b0 == b2) l0 = 1, l1 = 3, r0 = 2, r1 = 4, mip = b0, mxp = b1;
    else l0 = 1, l1 = 4, r0 = 2, r1 = 3, mip = b1, mxp = b0;
    if (mip > mxp) swap(mip, mxp), swap(l0, r0), swap(l1, r1);
    for (int i : views::iota(4, n)) {
        int val = ask(l0, r0, i);
        if (val < mip) answer(l1, mip), l1 = i, mip = val;
        else if (val == mip) answer(l0, mip), l0 = i, mip = ask(l0, l1, r0);
        else if (val > mip && val < mxp) answer(i, val);
        else if (val == mxp) answer(r0, mxp), r0 = i, mxp = ask(r0, r1, l0);
        else answer(r1, mxp), r1 = i, mxp = val;
    }
}

:::