题目大意

原题：CF Round 1093 Div2 D2 - Unique Values (Hard version)（rating 1900）

交互题。有一个长度 $2n+1$ 的隐藏数组 $a$ ，元素值在 $[1, n]$ 之间；其中有且仅有一个值出现 3 次，其余每个值都恰好出现 2 次。要求找出那个出现 3 次的值的三个下标。

每次询问可以选一个下标子集 $S$ ，judge 会返回 $\{a_i : i \in S\}$ 这个多重集里恰好出现一次的值的个数（即把一对一对的去掉以后还剩几种）。

Easy version: $\le 50$ 次询问。Hard version（本题）： $\le 33$ 次询问。 $n \le 1000$ 。

思路讲解

一句话

设那个特殊值（出现 3 次的）为 $T$ ，三个位置 $p_1 < p_2 < p_3$ 。33 次预算 = 3 段二分 × 11 次——每段用 bit-trick 在长度 $\le 2n+1 \le 2001$ 的范围里锁一个位置， $\lceil \log_2 2001 \rceil = 11$ 。三段分别独立设计一个关于 $k$ 单调的奇偶谓词，bit-trick 收敛。

核心 trick：贡献奇偶表

对任一询问集合 $S$ ，记 $\text{len} = |S|$ ， $\text{res}$ 为 judge 返回值。每个值 $v$ 对 $\text{len} - \text{res}$ 的贡献只取决于它在 $S$ 中的 count：

count	贡献 = count − [count==1]	奇偶
0	0	偶
1	0	偶
2	2	偶
3	3	奇

关键不变量：只有 count = 3 那档贡献奇数。本题里能让某个值 count = 3 的，只有那个出现 3 次的特殊值 $T$ 。所以 $(\text{len} - \text{res}) \bmod 2 = 1 \iff T \text{ 在 } S \text{ 里凑齐 } 3 \text{ 个 position}$ 。

其他值（出现 2 次的 double）count $\le 2$ ，贡献全偶，自动从奇偶位上消失——这就是奇偶谓词的威力，doubles 不来添乱。

第 1 段：找 $p_3$

询问 $S_k = [1..k]$ 。 $T$ 在 $S_k$ 里 count = 3 当且仅当 $k \ge p_3$ （三个位置全进来）。

$(k - \text{res}) \bmod 2 = 0 \iff k < p_3$

谓词在 $[0, p_3 - 1]$ 真， $[p_3, N]$ 假。bit-trick 从 $k = 0$ 起按 $2^i$ 加位，找最大的真 $k$ = $p_3 - 1$ ，加 1 即 $p_3$ 。

ll pos3 = 0;
for (int i = __lg(N); i >= 0; --i) {
    ll k = pos3 + (1ll << i);
    if (k > N) continue;
    ll res = query(1, k);
    if ((k - res) % 2 == 0) pos3 = k;
}
pos3++;

第 2 段：找 $p_1$

知道 $p_3$ 后，询问 $S_k = [k..p_3]$ （后缀）。 $T$ 在 $S_k$ 里 count = 3 当且仅当 $k \le p_1$ （三个位置都在 $[k..p_3]$ 里）。

$(\text{len} - \text{res}) \bmod 2 = 0 \iff k > p_1$

谓词在 $[p_1+1, p_3]$ 真， $[1, p_1]$ 假。bit-trick 从 $k = p_3$ 起降序减位，找最小的真 $k$ = $p_1 + 1$ ，减 1 即 $p_1$ 。

ll pos1 = pos3;
for (int i = __lg(pos3); i >= 0; --i) {
    ll k = pos1 - (1ll << i);   // ← 用当前 pos1，不是 pos3
    if (k < 1) continue;
    ll res = query(k, pos3);
    ll len = pos3 - k + 1;
    if ((len - res) % 2 == 0) pos1 = k;
}
pos1--;

第 3 段：找 $p_2$ （最绕的一段）

$p_1, p_3$ 已知，找 $p_2 \in (p_1, p_3)$ 。这一段最容易写错——不要用「query $[1..k] \setminus \{p_1, p_3\}$ 看 res 是否为 0」这种谓词，那个不单调。

正确设计：让 $T$ 在询问集合里的 count 在 $k$ 跨过 $p_2$ 时从 2 跳到 3（正好覆盖贡献表里的奇偶分界点）。

$S_k = \{p_3\} \cup [p_1..k], \quad k \in [p_1, p_3 - 1]$

T 在 $S_k$ 里： $p_1$ 必入（在 $[p_1..k]$ 里）， $p_3$ 必入（显式塞）， $p_2$ 当且仅当 $k \ge p_2$ 时入。

$k$ vs $p_2$	$T$ count	$(\text{len}-\text{res}) \bmod 2$
$k < p_2$	2	0（偶）
$k \ge p_2$	3	1（奇）

谓词 $\iff k < p_2$ ，bit-trick 从 $k = p_1$ 起加位，找最大真 $k$ = $p_2 - 1$ ，加 1 即 $p_2$ 。

ll pos2 = pos1;
for (int i = __lg(pos3 - pos1); i >= 0; --i) {
    ll to = pos2 + (1ll << i);
    if (to >= pos3) continue;
    auto [len, res] = query(pos1, to, pos1, pos3);   // [pos1..to] ∪ {pos1, pos3}
    if ((len - res) % 2 == 0) pos2 = to;
}
pos2++;

询问数核账

段	范围	bit 数上界
$p_3$	$[1, 2n+1]$	$\lceil \log_2 (2n+1) \rceil \le 11$
$p_1$	$[1, p_3]$	$\lceil \log_2 p_3 \rceil \le 11$
$p_2$	$[p_1, p_3 - 1]$	$\lceil \log_2 (p_3 - p_1) \rceil \le 11$

合计 $\le 33$ ，正好卡到题目限制。Easy version 给 50 次相对宽松，Hard 这 33 次每段都不能浪费一次询问——所以三个 bit-trick 必须用 continue 越界保护省下不必要的查询。

AC 代码

AC 提交链接

展开完整 C++ 源码

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define SZ(a) ((long long) a.size())

using namespace std;
using ll = long long;

ll lT, testcase;

ll query(const vector<ll> &posLs) {
    cout << "? " << SZ(posLs) << " ";
    for (auto p: posLs) cout << p << " ";
    cout << endl;
    ll res;
    cin >> res;
    return res;
}

ll query(ll l, ll r) {
    vector<ll> posLs;
    for (int i = l; i <= r; ++i) posLs.push_back(i);
    return query(posLs);
}

pair<ll, ll> query(ll l, ll r, ll pos1, ll pos3) {
    vector<ll> posLs;
    set<ll> st = {pos1, pos3};
    for (int i = l; i <= r; ++i) st.insert(i);
    posLs.reserve(SZ(st));
    for (auto p: st) posLs.push_back(p);
    return {SZ(posLs), query(posLs)};
}

void Solve() {
    ll N;
    cin >> N;
    N = 2 * N + 1;

    // 第 1 段: 找 p3
    ll pos3 = 0;
    for (int i = __lg(N); i >= 0; --i) {
        ll k = pos3 + (1ll << i);
        if (k > N) continue;
        ll res = query(1, k);
        if ((k - res) % 2 == 0) pos3 = k;
    }
    pos3++;

    // 第 2 段: 找 p1
    ll pos1 = pos3;
    for (int i = __lg(pos3); i >= 0; --i) {
        ll k = pos1 - (1ll << i);
        if (k < 1) continue;
        ll res = query(k, pos3);
        ll len = pos3 - k + 1;
        if ((len - res) % 2 == 0) pos1 = k;
    }
    pos1--;

    // 第 3 段: 找 p2 (强制塞 {p1, p3} 当 baseline)
    ll pos2 = pos1;
    for (int i = __lg(pos3 - pos1); i >= 0; --i) {
        ll to = pos2 + (1ll << i);
        if (to >= pos3) continue;
        auto [len, res] = query(pos1, to, pos1, pos3);
        if ((len - res) % 2 == 0) pos2 = to;
    }
    pos2++;

    cout << "! " << pos1 << " " << pos2 << " " << pos3 << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> lT;
    for (testcase = 1; testcase <= lT; ++testcase) Solve();
    return 0;
}

心路历程（WA → MLE → AC，被 D2 教做人的 4 个小时）

这道题头一次过 D1（Easy 50 次询问）那版还挺顺，三段二分各用 17 次差不多卡进去就完了。到 D2 把预算压到 33 次才开始遭罪——核心不是"次数压紧"这件事，而是 $p_2$ 那段我第一版完全写歪了思路，后面几次提交几乎都是在为最初这个错误的设计买单。

❌ 第一版：用 `!res` 当谓词，谓词根本不单调

第一版的想法是「query $[1..k] \setminus \{p_1, p_3\}$ ，看 res 是不是 0」。直觉是「subset 里所有值都成对了 = res = 0 = 还没碰到 $p_2$ 」，然后 bit-trick 找最大的 res = 0 的 $k$ 。

第一次提交：WA on test 1。看了一会才发现一个特别傻的低级错误：

1 2	plus(pos2, 1); // 这行返回值被丢了！ cout << "! " << pos1 << " " << pos2 << " " << pos3 << endl;

plus 是个按值收 pos2 的纯函数返回新值，我没赋值回来。pos2 全程是 0，输出 ! 1 0 3 直接非法。改成 pos2 = plus(pos2, 1)。

❌ 修了 line 179 后才发现：`!res` 这个谓词本身就不单调

修完那个赋值，跑反例 $a = [1, 2, 3, 2, 1, 3, 1]$ （ $T=1$ ， $p_2 = 5$ ）发现：

$k$	subset 值	res
0	$\varnothing$	0
2	$\{2\}$	1
3	$\{2, 3\}$	2
4	$\{2, 3, 1\}$	3
5	$\{2, 3, 1, 1\}$	2
6	$\{2, 3, 1, 1, 2\}$	1

res = 0 只在 $k = 0$ 出现一次，bit-trick 完全收敛不到 $p_2 - 1$ 。res = 0 要求 (a) $p_2 > k$ 且 (b) 所有 doubles 在 $[1..k]$ 里都凑成对——条件 (b) 完全取决于数组排列，不单调，bit-trick 没救。

✅ 重新设计：让 $T$ 的 count 落在贡献奇偶分界点 $2 \to 3$

被这个反例打醒以后回去想，关键是奇偶性技巧。每个值对 $\text{len} - \text{res}$ 的贡献只看 count，count = 3 那档唯一贡献奇数。所以谓词应该让 $T$ 的 count 在 $k$ 跨过 $p_2$ 时正好从偶（=2）跳到奇（=3）。

解法：强制把 $p_1$ 和 $p_3$ 塞进询问当 baseline，让 $T$ count 起步 = 2；可变前缀 $[p_1+1..k]$ 决定 $p_2$ 进不进来。doubles 全偶贡献，自动失声。

这一刻才意识到为什么 Easy 给 50 次而 Hard 卡 33 次——Hard 是逼你想出贡献奇偶表那张图，否则你写一段「 $\text{res} == 0$ 」走 32 次询问的解法在 Easy 能水过去（其实也水不过去因为不收敛），但 Hard 必须靠奇偶性拿满 11 + 11 + 11。

❌ 第二版：query 函数签名想得不干净

写了个 query(pos1, to, pos1, pos3) 4-arg 重载，意思是 [pos1..to] ∪ {pos1, pos3}。Claude 提醒 pos1 重复传了（既是区间端点又是 extra），但实测因为内部用 set<ll> 去重，功能上没坏。算是一个"看起来丑但实际能跑"的设计——code review 视角不优雅，但提交跑下来对的，就先不动它了。

❌ 第三版：`to` 没卡上界 → MLE on test 2

写完 $p_2$ 那段提交：MLE on test 2，262100 KB / 256 MB。看了一会想不通：算法里 vector<ll> 都是局部变量，每次 query 完就析构，per-query 内存几 KB，单次 Solve $\le$ 100 KB，怎么会到 256 MB？

最后定位到 line 173 没卡 to < pos3：

for (int i = __lg(pos3 - pos1); i >= 0; --i) {
    ll to = pos2 + (1ll << i);
    // 没有越界保护！
    auto [len, res] = query(pos1, to, pos1, pos3);
    ...
}

bit-trick 推进时，trial 值 to 可以超过 pos3 甚至 N = 2n+1——比如 $p_3 \approx 2000$ , $p_{2,\text{actual}} \approx 1500$ , $p_1 = 1$ 这种局，几次 take 之后 pos2 ~ 1985，下一轮 $i=5$ 算出 to = 2017 > N，把 $2002, ..., 2017$ 这种不存在的位置全发给 judge。Judge 返 -1，但代码不退出继续读流，stream 关掉以后所有 cin 都 fail（C++11+ 落 res = 0），predicate 退化成"按 k 奇偶决定 take"，状态彻底污染。

Per problem statement: After receiving such a response, your program should immediately terminate.

我没退出，导致后面跑成什么样都不可控——MLE 大概率是 stdout pipe 被 judge 关掉以后 iostream 缓冲区累积，或者多 test cases 在烂状态下连续跑出来的 cascade。根因是单次 invalid query 没立刻退出。

修法：

1 2	ll to = pos2 + (1ll << i); if (to >= pos3) continue; // ← 补这一行

顺手把 $p_3$ 段 if (k > N) continue; 和 $p_1$ 段 if (k < 1) continue; 也补了——这俩同样能越界，只是没造成 MLE。

❌ 第四版：`p_1` 段 bit-trick 写错变量

补完三处 continue 还过不了。再仔细看 $p_1$ 段：

for (int i = __lg(pos3); i >= 0; --i) {
    ll k = pos3 - (1ll << i);   // ← 用了 pos3 不是 pos1!
    ...
    if (...) pos1 = k;
}

bit-trick 降序的标准套路是每轮用当前的 pos1****（已经被前几轮压低过）减 $2^i$ 当 trial 值，让 pos1 单调下降收敛到 $p_{1,\text{actual}} + 1$ 。我写成 pos3 - (1ll << i)， $p_3$ 整个循环不变，每轮 trial 都是固定的 $p_3 - 2^i$ 那 11 个偏移量——根本不是 bit-trick，最后 pos1 等于最后一次 predicate 真的那个 $k$ ，几乎一定是 $p_3 - 1$ （除非 $p_{1,\text{actual}} = p_3 - 1$ ）。

为什么 sample 蒙过了：sample 是 $p_1 = 1, p_3 = 3$ ，循环只 2 轮，恰好 $i=0$ 时 $k = p_3 - 1 = 2$ 就是 $p_{1,\text{actual}} + 1$ ，pos1 = 2，pos1-- = 1。完美对的——但完全是巧合。

改成 ll k = pos1 - (1ll << i);，提交：AC。提交号 374001488。

总结一下踩过的坑

lambda 返回值丢了——低级 typo 但确实写过，下次 IDE warning 多看一眼
!res 不单调——奇偶谓词 vs 等于零谓词的认知差。等于零是偶发性的、依赖排列；奇偶性才是结构性的，doubles 自动失声
bit-trick trial 值没卡上界——3 个段都要保护：k > N / k < 1 / to >= p_3。MLE 不是因为单次内存，是因为没有遵守 read -1 → exit 的协议，状态污染后续的 cascade 才把内存搞炸的
bit-trick 用了静态变量代替累积变量——pos3 - 2^i vs pos1 - 2^i，sample 巧合下还能过，靠肉眼看完全看不出来，必须自己手算几个反例
Easy → Hard 不是单纯次数压紧——往往 Hard 在逼你换更结构化的 idea。这道题 Hard 的 33 次是直接告诉你"每段必须 $\lceil \log_2 N \rceil$ 不能浪费"，反推奇偶谓词的设计

附件

📄 p2 奇偶谓词的设计思路（独立讲解 PDF，含贡献奇偶表 + 反例数组完整 trace）

D2_Unique_Values_Hard_version.cpp.txt

题目大意

思路讲解

一句话

核心 trick：贡献奇偶表

第 1 段：找 p3p_3p3​

第 2 段：找 p1p_1p1​

第 3 段：找 p2p_2p2​ （最绕的一段）