[loj3834] [IOI2022] 最罕见的昆虫 - 交互 - 二分

传送门：https://loj.ac/p/3834
题目大意： $n$ 个物品，每个物品属于一种类别。你需要维护一个物品集合，初始为空。支持操作：将某个不在集合中的物品放入集合；将某个集合中的物品移出集合；查询集合中出现次数最多的种类的出现次数。你需要回答：所有物品中出现次数最少的种类的出现次数。要求插入、删除、查询操作的次数分别不超过 $3n$ 次。
解：最暴力的思想是，将所有物品两两放入集合中查询，根据返回 $1$ 还是 $2$ 可判断两个物品是否种类相同，然后就能直接求出每种物品的数量了。但这需要 $O(n^2)$ 次操作。
考虑优化这一过程。首先我们希望找出所有的种类（或者说，找到所有种类的物品各一个）。我们可以设计出如下算法：每次向集合中加入一个物品并查询，如果结果为 $2$ ，说明它与先前某个物品种类相同，就将它取出集合，否则说明它是一个新的种类，将其留在集合中。如此处理完所有元素后，集合中剩下的就恰好是所有种类的物品各一个了。如此我们还可以得到种类的数量，下文记作 $m$ ，集合中剩余的元素我们称为每个种类的“代表元”。
接下来进行一个“整体二分”的操作（或者称为“二进制分组”）：将种类编号为 $0\sim m-1$ ，接下来进行 ${\log }_{2}m$ 轮操作，每一轮中仅在集合中保留二进制第 $i$ 位为 $1$ 的种类的代表元，然后依次加入每个剩余的元素并查询，如果结果为 $2$ ，说明集合中有元素与它种类一致，就说明当前元素的种类编号的二进制第 $i$ 位为 $1$ ，反之若查询结果为 $1$ 则说明当前元素的种类编号的二进制第 $i$ 位为 $0$ 。查询完后立刻将被查询元素取出集合。如此便可以确定每个元素所属的种类，但这仍需 $O(n\log n)$ 次操作。
我们需要进一步优化！需要注意到，其实确定每个元素具体属于哪个类别并不一定是必要的，因为我们只关心最小的那个类别的大小。
受此启发，我们可以得到另外一种处理方式：在第一轮确定代表元之后把集合清空，再用所有非代表元的元素跑一遍相同的过程。这样仍然可以在集合中留下一些代表元，注意其数量 $m^{\prime }$ 与 $m$ 的关系：显然有 $m^{\prime }\le m$ ，但若 $m^{\prime }<m$ 说明什么？说明某种类别只在第一轮的 $m$ 个代表元中出现过，而在后面压根没出现过！由此可以立即确定所求的答案为 $1$ 。如果 $m^{\prime }=m$ ，则说明所求答案至少为 $2$ ，可以继续之前的操作，直到某一轮中留下的代表元数量小于 $m$ 为止。
但是，上述过程在 $m$ 很小时操作次数仍然很大。如何优化？考虑到上述过程本质上就是枚举答案的过程，我们可以将枚举答案改为二分答案。在每一轮中，假设还剩余 $k$ 个物品，则这些元素对答案的贡献可能在 $0\sim \lfloor \frac{k}{m}\rfloor$ 之间，我们选取 $mid=\lfloor \frac{\lfloor \frac{k}{m}\rfloor +1}{2}\rfloor$ ，检查是否这 $m$ 个种类在这 $k$ 个元素中出现次数均至少为 $mid$ 。我们先将集合清空，然后依次加入元素并询问，一旦出现询问结果为 $mid+1$ 的情况，就将元素取出集合。如此下来，如果最后集合中的元素数量恰为 $m\times mid$ ，就说明答案至少为 $mid$ ，否则说明答案不到 $mid$ 。
关键在于，无论是上述哪种情况，我们在下一轮都只需要保留一半的元素。如果是前一种情况 ，那么当前轮的这 $m\times mid$ 个代表元显然就可以直接扔掉，最后在答案中加上 $mid$ 即可；而如果是后一种情况，那么被取出集合的那些元素就无需在下一轮中考虑了，因为他们一定是属于某个大于 $mid$ 的类别，而最终的答案一定小于 $mid$ ，因此只需要继续处理现在集合内剩余的元素即可。
如此我们算一下操作次数： $n+n+n/2+n/4+n/8+...=3n$ 刚好满足要求。需要注意的是，后面的二分操作可能牵扯到取整的问题，造成每次留下的元素比一半多一点，误差的积累可能造成最终的操作次数略大于 $3n$ 。解决办法也比较简单：每次随机打乱剩余元素，然后在加入时一旦发现当前集合已满 $m\times mid$ 就停止即可。同时 $mid$ 的选取为 $\lfloor \frac{\lfloor \frac{k}{m}\rfloor +1}{2}\rfloor$ 而非 $\lfloor \frac{k}{2m}\rfloor$ 也是考虑到了这一因素。
代码如下：

#include
#include "insects.h" 
using namespace std;
#define li long long
#define in move_inside
#define out move_outside
#define chk press_button
li s1 = 19491001,s2 = 23333333,s3 = 998244853,srd;
inline li rd(){
	return srd = (srd * s1 + s2 + rand()) % s3;
}
int n,a[2010],b[2010],c[2010],p1,p2,p3;
int min_cardinality(int _n){
	n = _n;p1 = p2 = p3 = 0;
	srand(time(0));rd();
	int i,j;
	for(i = 0;i < n;++i){
		in(i);
		if(chk() == 2){
			out(i);a[++p1] = i;
		}
		else b[++p2] = i;
	}
	int ans = 1,cnt = p2;
	if(cnt == 1) return n;
	if(cnt > n / 2) return 1;
	while(p2) out(b[p2--]);
	while(p1 >= cnt){
		for(i = 1;i <= p1;++i) swap(a[i],a[rd() % i + 1]);
		int mid = (p1 / cnt + 1) / 2;
		for(i = 1;i <= p1;++i){
			if(p3 == mid * cnt) break;
			in(a[i]);
			if(chk() > mid){
				out(a[i]);b[++p2] = a[i];
			}
			else c[++p3] = a[i];
		}
		for(;i <= p1;++i) b[++p2] = a[i];
		if(p3 == mid * cnt){
			ans += mid;
			for(i = 1;i <= p2;++i) a[i] = b[i];
			p1 = p2;
		}
		else{
			for(i = 1;i <= p3;++i) a[i] = c[i];
			p1 = p3;
		}
		while(p3) out(c[p3--]);
		p2 = p3 = 0;
	}
	return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53