题解：交互式二分查找确定等价类算法

问题分析

本题是一个交互式问题，需要确定 $N$ 个朋友中哪些人穿相同服装。关键限制是：

1. 每次聚会只能知道邀请的朋友中不同服装的种类数
2. 不能知道具体谁穿什么服装
3. 聚会次数有限制（最好 ≤ 3500）

需要设计高效的询问策略来确定朋友之间的等价关系（穿相同服装）。

核心算法思路

基本观察

• 如果将朋友按服装类型分组，我们实际上是要找出这 $C$ 个等价类
• 对于新朋友 $i$，我们需要确定他属于已有的哪个等价类，或者创建一个新类
• 每次查询返回的是不同服装种类数，这本质上反映了集合的基数

算法框架：在线插入与二分查找

算法维护：

1. ans[i]：朋友 $i$ 所属的服装类型编号（从 1 开始）
2. pos[j]：第 $j$ 类服装的一个代表朋友（用于查询）

对于每个新朋友 $i$（按顺序处理）：

1. 检查是否属于新类：

   • 邀请所有已有类的代表朋友（pos[1] 到 pos[m]）加上朋友 $i$
   • 如果返回结果 ≠ $m$（即种类数增加），说明 $i$ 的服装与所有已有类都不同
   • 此时创建新类：m++，ans[i] = m，pos[m] = i

2. 二分查找所属类：

   • 如果 $i$ 的服装与某个已有类相同
   • 在 [1, m] 范围内二分查找 $i$ 属于哪个类
   • 关键性质：对于区间 [l, r]，如果邀请 pos[l..r] 加上 $i$，返回结果等于 r-l+1
     • 如果为真：说明 $i$ 的服装与 pos[l..r] 中某人的相同（种类数没增加）
     • 如果为假：说明 $i$ 的服装与 pos[l..r] 中所有人的都不同

算法正确性证明

查询函数的设计

qry(l, r, ex) 函数邀请：

• pos[l] 到 pos[r]：这些是不同服装类的代表
• ex：要测试的新朋友 $i$

返回结果分析：

• 如果 $i$ 的服装与 pos[l..r] 中某人的相同：结果 = r-l+1
• 如果 $i$ 的服装与 pos[l..r] 中所有人的都不同：结果 = r-l+2

二分查找的正确性

假设 $i$ 的服装与第 $j$ 类相同：

• 对于任意包含 $j$ 的区间 [l, r]，查询结果 = 区间长度（因为 $i$ 的服装已存在）
• 对于不包含 $j$ 的区间，查询结果 = 区间长度 + 1（增加新种类）

因此二分查找能够准确定位 $j$。

复杂度分析

聚会次数

• 对于第 $i$ 个朋友：
  1. 初始检查：1 次查询
  2. 如果属于已有类：二分查找需要 $O(\log C)$ 次查询，其中 $C$ 是当前类别数
• 总查询次数：$O(N \log N)$
• 最坏情况：所有服装都不同（$C = N$），总查询数 ≈ $N \log N$
• 对于 $N=150$，最坏约 $150 \times 8 = 1200$ 次，远小于 3500 的限制

时间复杂度

• 每次处理一个朋友：$O(\log N)$ 次查询
• 总时间：$O(N \log N)$，对于 $N \le 150$ 完全可行

空间复杂度

• $O(N)$ 存储答案和代表朋友

算法优势

1. 在线算法：逐个处理朋友，不需要预先知道 $C$
2. 确定性算法：不依赖随机化，保证正确性
3. 查询高效：利用二分查找将线性搜索优化为对数级别
4. 实现简单：代码简洁，逻辑清晰

总结

本题展示了一种巧妙的交互式二分查找确定等价类的方法，主要考察：

1. 问题转化能力：将服装识别问题转化为集合基数查询问题
2. 在线算法设计：逐个处理元素，动态维护等价类
3. 二分查找应用：在不能直接比较元素的情况下，通过集合查询间接定位
4. 交互策略优化：利用已知信息减少不必要的查询

算法的核心洞见在于：

• 使用各类代表构成测试集，通过查询结果推断新元素的归属
• 利用二分查找将 $O(C)$ 的线性搜索优化为 $O(\log C)$
• 维护最小必要信息（每类一个代表）来支持高效查询

这种"代表集合+二分查找"的交互策略在类似问题中具有通用性，是解决不可直接比较元素的分类问题的有效范式。