题解：P14134 【MX-X22-T5】「TPOI-4E」Get MiN? Get MeX!

· · 题解

确定性，太困难。

这是一种非确定性算法，期望询问次数 \log n + \operatorname O (1)。

首先观察一下 35 大概是 \log 级别，考虑二分。

二分就是每次把当前集合分成大小为 \left \lfloor {n \over 2} \right \rfloor 和 \left \lceil {n \over 2} \right \rceil 的两部分，保留一部分，舍弃另一部分。

假设当前集合中没有 1，那么 0 所在部分的第一类询问就会返回 1，而另一部分的第一类询问就会返回 \ge 2。

所以大概想法就是，在第一次二分中把 1 给踢出去。

具体地，在第一次二分中不断把集合随机分成大小为 \left \lfloor {n \over 2} \right \rfloor 和 \left \lceil {n \over 2} \right \rceil 的两部分，直到大小为 \left \lfloor {n \over 2} \right \rfloor 的部分的第一类询问返回 1 为止。

上述过程后，一定能够保证 0 和 1 在不同的集合中，否则第一类询问会返回 \ge 2。成功概率 1 \over 2，期望次数为 2 次。

在这之后，还需确定 0 在哪一部分。

这时候可以对某一部分分别问一次第一类操作和第二类操作，返回值相等说明 0 在另一部分，反之则在这一部分。

在第一次二分之后，每次二分若第一类询问返回 1 则保留该部分，否则保留另一部分，直到剩下的集合大小为 1 为止。

第一次二分期望 2 + 1 + 1 = 4 次，之后每次二分只需 1 次，总期望 \log n + \operatorname O (1)。