CF Round 1093 Div2 D2 - Unique Values (Hard version) · znzryb
# 题目大意
[原题:CF Round 1093 Div2 D2 - Unique Values (Hard version)](https://codeforces.com/contest/2220/problem/D2)(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$ 。
```cpp
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$ 。
```cpp
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$ 。
```cpp
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 提交链接**](https://codeforces.com/contest/2220/submission/374001488)
::: 展开完整 C\+\+ 源码
```cpp
#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**。看了一会才发现一个**特别傻的低级错误**:
```cpp
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`:
```cpp
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 没立刻退出**。
修法:
```cpp
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$ 段:
```cpp
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](https://codeforces.com/contest/2220/submission/374001488)。
## 总结一下踩过的坑
1. **lambda 返回值丢了**——低级 typo 但确实写过,下次 IDE warning 多看一眼
1. **`!res`** **不单调**——奇偶谓词 vs 等于零谓词的认知差。等于零是偶发性的、依赖排列;奇偶性才是结构性的,doubles 自动失声
1. **bit-trick trial 值没卡上界**——3 个段都要保护:`k > N` / `k < 1` / `to >= p_3`。MLE 不是因为单次内存,是因为**没有遵守** **`read -1 → exit`** **的协议**,状态污染后续的 cascade 才把内存搞炸的
1. **bit-trick 用了静态变量代替累积变量**——`pos3 - 2^i` vs `pos1 - 2^i`,sample 巧合下还能过,靠肉眼看完全看不出来,必须**自己手算几个反例**
1. **Easy → Hard 不是单纯次数压紧**——往往 Hard 在逼你换更结构化的 idea。这道题 Hard 的 33 次是直接告诉你"每段必须 $\lceil \log_2 N \rceil$ 不能浪费",反推奇偶谓词的设计
# 附件
[📄 p2 奇偶谓词的设计思路(独立讲解 PDF,含贡献奇偶表 + 反例数组完整 trace)](https://media.znzryb.com/20260509-d4f8b903/pos2_parity_explained_71cef440.pdf)
[D2_Unique_Values_Hard_version.cpp.txt](https://prod-files-secure.s3.us-west-2.amazonaws.com/991df910-3fbe-4ef6-8683-a51746ed5b66/f099baea-0c31-4c9c-be82-e3aabd44522a/D2_Unique_Values_Hard_version.cpp.txt?X-Amz-Algorithm=AWS4-HMAC-SHA256&X-Amz-Content-Sha256=UNSIGNED-PAYLOAD&X-Amz-Credential=ASIAZI2LB4662H4IDEEH%2F20260511%2Fus-west-2%2Fs3%2Faws4_request&X-Amz-Date=20260511T130035Z&X-Amz-Expires=3600&X-Amz-Security-Token=IQoJb3JpZ2luX2VjEEwaCXVzLXdlc3QtMiJHMEUCIQDztS3YDiqMUn%2BDnNFYNclGnJM7zlfLefrO2CBbSXrL6AIgcyvRUzKulLF2WyOHidGJyjjzGHyu8JRVHOxerHduHtwq%2FwMIFRAAGgw2Mzc0MjMxODM4MDUiDJBirN1Xfl5syIhj2SrcA34%2BZTagB2fZrWzvim0yOWDOFJGspiVYLIRDELuuJvWMSaXvg0ptI6Zeda%2FSYoi71ixUELBn3xLpVxueEVpm5izCMAUpuW783vDC1vy6ikW58jeVIzmuUQSh7IG6781VL%2BV1BmfdTFaHqNvrwCqLC%2FjZ50K0EymlWUg%2Fk4oc%2B8CBNKCldXGeFYE46PJ%2FQdtYcoG348wgM%2FMWXr9aKeriioHncSSqnKG9EEiElOV1KDP5LmjNFE%2FQQIvCCYNc8jveBHmgBdX9goJ%2Bz%2FYbINyyXNPip%2BDgy%2B2gGxdCwqls42B0uDAd2r786KLcbkzBxybbYXqPjDsrDmXf33JxBZ%2FTsdwD6bE%2FyW44islDAVUaMQLKVnn3vsbNJ%2FX0IKG4bBtxLkf%2Bca%2FvFkzt6x3%2BAUhGxvPu5uwufu6j1UmkL0bhs0jWbYeDIw7OYXufYmZWk9oSdc2yk3FrsV9bJM3hJqpnKpZGdEJ8ZDWzPIk9m93aRqjO6JzMXCqdfEirxM%2BkiHlVSrJxZCy5lE1UVmUqwRxW%2B6faHeM%2FIcNyDnOhBONhvGxcqnaElwMQTl29LACwtHKDQJNPHkU4LoKr9su3ZAnekAcDMVG2HlRxYHQBFJZUP5NBcv%2F8zopCm%2FyM2w73MMWRh9AGOqUBUD3MzIrSvyJeDSisrS9ymIrx%2FL5wHGVM5Svq9SV7Sii0u1vVTV0w4BRlB%2F%2FVxMVtx6Os1DXgEqfqMrCxY5wxz8mPsJlOV8yASx8jfLDrvu09P6aTuKpjzk37I1sJqkzr9U5jJF%2FQKsVPpKHDqhu2eEJF49ub3RdqLo7fTS1Kp2%2B6pvrdFObmwuY9%2BkebDJS%2B6ZmEsojieJZNnU7v1BOt7WpHXj85&X-Amz-Signature=21856e42beb2b6873a3ac4945c70ffa3671ffd87c1bf6f0e7aee44507e98eec1&X-Amz-SignedHeaders=host&x-amz-checksum-mode=ENABLED&x-id=GetObject)
[📄 p2 奇偶谓词的设计思路(独立讲解 PDF,含贡献奇偶表 + 反例数组完整 trace)](https://media.znzryb.com/20260509-d4f8b903/pos2_parity_explained_b7eb212d.pdf)
[D2_Unique_Values_Hard_version.cpp.txt](https://prod-files-secure.s3.us-west-2.amazonaws.com/991df910-3fbe-4ef6-8683-a51746ed5b66/c5bdfa1d-238c-4629-841e-f1910cab59e8/D2_Unique_Values_Hard_version.cpp.txt?X-Amz-Algorithm=AWS4-HMAC-SHA256&X-Amz-Content-Sha256=UNSIGNED-PAYLOAD&X-Amz-Credential=ASIAZI2LB4662H4IDEEH%2F20260511%2Fus-west-2%2Fs3%2Faws4_request&X-Amz-Date=20260511T130035Z&X-Amz-Expires=3600&X-Amz-Security-Token=IQoJb3JpZ2luX2VjEEwaCXVzLXdlc3QtMiJHMEUCIQDztS3YDiqMUn%2BDnNFYNclGnJM7zlfLefrO2CBbSXrL6AIgcyvRUzKulLF2WyOHidGJyjjzGHyu8JRVHOxerHduHtwq%2FwMIFRAAGgw2Mzc0MjMxODM4MDUiDJBirN1Xfl5syIhj2SrcA34%2BZTagB2fZrWzvim0yOWDOFJGspiVYLIRDELuuJvWMSaXvg0ptI6Zeda%2FSYoi71ixUELBn3xLpVxueEVpm5izCMAUpuW783vDC1vy6ikW58jeVIzmuUQSh7IG6781VL%2BV1BmfdTFaHqNvrwCqLC%2FjZ50K0EymlWUg%2Fk4oc%2B8CBNKCldXGeFYE46PJ%2FQdtYcoG348wgM%2FMWXr9aKeriioHncSSqnKG9EEiElOV1KDP5LmjNFE%2FQQIvCCYNc8jveBHmgBdX9goJ%2Bz%2FYbINyyXNPip%2BDgy%2B2gGxdCwqls42B0uDAd2r786KLcbkzBxybbYXqPjDsrDmXf33JxBZ%2FTsdwD6bE%2FyW44islDAVUaMQLKVnn3vsbNJ%2FX0IKG4bBtxLkf%2Bca%2FvFkzt6x3%2BAUhGxvPu5uwufu6j1UmkL0bhs0jWbYeDIw7OYXufYmZWk9oSdc2yk3FrsV9bJM3hJqpnKpZGdEJ8ZDWzPIk9m93aRqjO6JzMXCqdfEirxM%2BkiHlVSrJxZCy5lE1UVmUqwRxW%2B6faHeM%2FIcNyDnOhBONhvGxcqnaElwMQTl29LACwtHKDQJNPHkU4LoKr9su3ZAnekAcDMVG2HlRxYHQBFJZUP5NBcv%2F8zopCm%2FyM2w73MMWRh9AGOqUBUD3MzIrSvyJeDSisrS9ymIrx%2FL5wHGVM5Svq9SV7Sii0u1vVTV0w4BRlB%2F%2FVxMVtx6Os1DXgEqfqMrCxY5wxz8mPsJlOV8yASx8jfLDrvu09P6aTuKpjzk37I1sJqkzr9U5jJF%2FQKsVPpKHDqhu2eEJF49ub3RdqLo7fTS1Kp2%2B6pvrdFObmwuY9%2BkebDJS%2B6ZmEsojieJZNnU7v1BOt7WpHXj85&X-Amz-Signature=038588d61b7c7db49832d0df652ff60d0f36a0facbab3da78d090d10033e92fd&X-Amz-SignedHeaders=host&x-amz-checksum-mode=ENABLED&x-id=GetObject)