hhz 杂题选讲。

IOI2023 最罕见的昆虫

我们考虑最小值具有什么性质。

将权值列出直方图，发现最小值下的数的个数都是 \(k\tiems num\) 种，这是最大值并且取到的。

实际上，这个是在说明最小值信息具有单调性。

那首先考虑问出种类数，我们可以一个一个加入并查询众数。这需要 \(n\) 次询问。

然后二分最小值，这也可以通过一个一个加入查询众数来计算出现 \(\le mid\) 次的点的个数。这并不复杂。

至于 \(O(n)\) 的做法，可以仿照类似 nth_element 方法，一次砍掉一半。

如何卡常？你可以再 \((l+r)\bmod 2=1\) 时随机加减。

询问的时候如果已经达到理论最大 \(k\times mid\) 那就退出。先shuffle效果很好。

---