Codeforces 558D Guess Your Way Out! II：差分映射解完全二叉樹出口推理

題目大意

深度 n 的完全二叉樹，葉子節點編號 [2^{n-1}, 2^n-1]。q 個提示：第 dep 層區間 [l, r] 是(1)/否(0)包含出口。判斷：唯一出口→輸出編號；多解→Data not sufficient!；矛盾→Game cheated!。

區間映射到葉子層

第 dep 層節點區間 [l, r] 對應葉子層區間：
重複 n-dep 次：l <<= 1; r = (r << 1) | 1;
得到葉子層區間 [L, R]。

差分統計覆蓋次數

• 提示「是」：diff[L]++, diff[R+1]--。
• 提示「否」：補集轉為兩個「是」區間：[leafL, L-1] 和 [R+1, leafR]，同樣差分更新。

掃描差分數組（用 map 稀疏存儲），累加覆蓋計數 cover。記錄 cover == q 的葉子區間總長度 cnt 與任一葉子編號 ans。
- cnt == 0 → 矛盾。
- cnt == 1 → 唯一出口 ans。
- cnt > 1 → 多解。

C++ 實現

 1) cout << "Data not sufficient!\n";
    else cout << ans << '\n';
    return 0;
}

複雜度

q ≤ 10^5，差分點 ≤ 4q，map 操作 O(log q)，總時間 O(q log q)。