CF2219B2.Unique Values (Hard version)

简单版与困难版的区别在于允许的查询次数上限不同。本题中最多允许进行 $33$ 次查询。

存在一个隐藏数组 $a$，长度为 $2n+1$，其中元素取值为 $1$ 到 $n$ 的整数。每个值恰好出现两次，但有且仅有一个值恰好出现三次。

你的任务是找出这个出现三次的值对应的三个位置。

你可以进行最多 $33$ 次如下形式的查询：

1. 选择一个整数 $k$，以及一个长度为 $k$ 的数组 $s$，其中包含 $1$ 到 $2n+1$ 之间的互不相同的下标。
2. 你会得到一个数值，表示在
   $a_{s_1}, a_{s_2}, \ldots, a_{s_k}$
   中，恰好出现一次的不同数值的个数（也就是说，没有重复的数的个数）。

例如，如果
$a_{s_1}, \ldots, a_{s_k} = {2, 1, 2, 3, 2, 3, 6, 7}$，
那么查询结果为 $3$，因为只有 $1, 6, 7$ 各出现一次。
数值 $3$ 出现了 $2$ 次，数值 $2$ 出现了 $3$ 次，都不只出现一次，因此不计入答案。

每个测试包含多组测试数据。

第一行是测试组数 $t$（$1 \le t \le 500$）。

接下来是每组测试数据：

• 每组第一行包含一个整数 $n$（$2 \le n \le 1000$）。

对于每组测试，隐藏数组 $a$ 是固定的，在交互过程中不会发生改变（即交互器不是自适应的）。

保证所有测试数据中 $n$ 的总和不超过 $2 \times 10^4$。

null

隐藏数组为：
$a = [1, 1, 1, 2, 2]$

• 第一次查询：询问区间 $[a_1, a_2] = [1, 1]$，因为 $1$ 出现了两次，没有只出现一次的数，所以答案为 $0$。
• 第二次查询：询问 $[a_1, a_4] = [1, 2]$，$1$ 和 $2$ 各出现一次，所以答案为 $2$。
• 第四次查询：询问
  $[a_1, a_2, a_3, a_4, a_5] = [1, 1, 1, 2, 2]$，
  所有数都出现多次，因此答案为 $0$。

最终输出：出现三次的值所在位置为 $1, 2, 3$。

部分内容由 GPT-5.3 辅助完成