题目重述

我们有 $2N$ 个矿物样本，属于 $N$ 种不同的矿物，每种矿物恰好有两个样本。
我们有一个设备，可以插入或取出样本，并返回当前设备中 不同矿物的种类数（不是样本数）。
我们可以进行最多 $10^6$ 次 Query(x) 操作，最终要用 Answer(a,b) 输出所有 $N$ 对匹配。

---

关键观察

设设备中当前有 $k$ 种矿物。

• 插入一个新样本 $x$：
  • 如果设备中已有同种矿物的另一个样本，则种类数不变（$k$ → $k$）
  • 如果设备中没有该矿物的样本，则种类数增加 1（$k$ → $k+1$）
• 取出一个样本 $x$：
  • 如果设备中还有该矿物的另一个样本，则种类数不变（$k$ → $k$）
  • 如果设备中这是该矿物的唯一样本，则种类数减少 1（$k$ → $k-1$）

因此，种类数的变化可以告诉我们样本之间的关系。

---

基础思路：逐个配对

最朴素的方法：
对于样本 $i=1 \dots 2N$，尝试与 $j>i$ 配对：
把 $i$ 放入设备，再把 $j$ 放入设备，看种类数是否增加 2（表示两个都是新矿物）或不变（表示 $i$ 和 $j$ 同种）。

但这样需要 $O(N^2)$ 次查询，不可行。

---

分治策略

我们可以利用 分治 来减少查询次数。

核心思想

假设我们已知两个样本集合 $A$ 和 $B$，且已知：

• $A$ 中样本的匹配都不在 $A$ 中（即匹配在 $B$ 或未知集合中）
• $B$ 中样本的匹配都不在 $B$ 中

那么我们可以用以下方法找出 $A$ 与 $B$ 之间的匹配：

1. 把 $A$ 中所有样本插入设备，记录种类数 $cnt_A$。
2. 对于 $B$ 中每个样本 $b$，插入 $b$：
   • 如果种类数增加 1，说明 $b$ 的匹配不在 $A$ 中
   • 如果种类数不变，说明 $b$ 的匹配在 $A$ 中

这样我们就能把 $B$ 分成 $B_{\text{match}}$（匹配在 $A$ 中）和 $B_{\text{other}}$（匹配不在 $A$ 中）。

分治过程

1. 把所有样本编号 $1 \dots 2N$ 随机排列，分成左右两半 $L$ 和 $R$。
2. 递归处理 $(L, R_{\text{match}})$ 和 $(L_{\text{match}}, R)$ 等子问题。

具体来说，我们维护一个“待匹配”集合 $S$，初始为 $\{1,\dots,2N\}$。
每次将 $S$ 随机分成大小相近的两半 $X$ 和 $Y$，用上述方法找出 $X$ 与 $Y$ 之间的匹配，并递归处理剩下的。

---

查询次数分析

设 $T(n)$ 为处理 $n$ 对匹配所需的查询次数（$|S|=2n$）。

一次分治：

• 插入 $X$ 所有元素：$|X|$ 次
• 对 $Y$ 每个元素查询一次：$|Y|$ 次
• 取出 $X$ 所有元素：$|X|$ 次（可选，为了清空设备）
• 递归：$T(k) + T(n-k)$，其中 $k$ 是找到的匹配对数

所以近似： $T(n) \approx 2|S| + T(k) + T(n-k)$ 最坏情况 $k \approx n/2$，则： $T(n) \approx 4n + 2T(n/2)$ 解得 $T(n) = O(n \log n)$。

对于 $N \le 4.3\times 10^4$，$T(N) \approx 4.3\times 10^4 \times \log_2(4.3\times 10^4) \approx 4.3\times 10^4 \times 16 \approx 6.9\times 10^5$，在 $10^6$ 限制内。

---

算法实现细节

数据结构

• 用 vector 存储当前待匹配的样本集合。
• 用栈或递归实现分治。

优化

• 避免重复插入：在递归过程中，保持设备状态或及时清空。
• 随机打乱：避免最坏情况。

伪代码

void solve(vector<int> samples) {
  if samples.size == 2:
    Answer(samples[0], samples[1])
    return
  
  随机打乱 samples
  mid = samples.size / 2
  X = samples[0..mid-1]
  Y = samples[mid..end]
  
  // 找出 X 与 Y 之间的匹配
  set device empty
  for x in X: Query(x)  // 插入 X
  cntX = 当前种类数（可通过最后一次Query得到）
  
  vector<int> matchY, otherY
  for y in Y:
    cnt_after = Query(y)  // 插入 y
    if cnt_after == cntX: // 种类数不变 → y 的匹配在 X 中
      matchY.push_back(y)
    else: // 种类数增加 → y 的匹配不在 X 中
      otherY.push_back(y)
    cntX = cnt_after
  
  // 清空设备：取出 X 和 matchY
  for x in X: Query(x)
  for y in matchY: Query(y)
  
  // 对 matchY，找出它在 X 中的匹配
  vector<int> matchX = find_match(X, matchY)  // 用同样方法
  
  // 递归
  solve(merge(matchX, matchY))  // 已匹配的对
  solve(merge(X \ matchX, otherY))  // 剩余
}

其中 find_match(A, B) 用同样查询方法找出 $A$ 中与 $B$ 匹配的元素。

---

公式总结

设 $C(S)$ 表示集合 $S$ 中的矿物种类数，则对于样本 $x$ 和集合 $A$：

$$C(A \cup {x}) - C(A) = \begin{cases} 0 & \text{$x$ 的匹配在 $A$ 中} \\ 1 & \text{否则} \end{cases} $$

这是整个算法的理论基础。

---

复杂度

• 查询次数：$O(N \log N)$
• 时间复杂度：$O(N \log N)$
• 空间复杂度：$O(N)$