E. Broken Queries 题解

题目回顾

这是一道交互题，核心规则：

1. 隐藏一个长度为 $n$（$n$ 是 $2$ 的幂）的二进制数组，恰好有一个 $1$，其余为 $0$；
2. 隐藏整数 $k(2\le k\le n-1)$，查询区间 $[l,r]$ 时：
   • 区间长度 $<k$：返回真实区间和（$1$ 表示 $1$ 在区间内，$0$ 反之）；
   • 区间长度 $\ge k$：返回取反后的结果；
3. 最多使用 $33$ 次查询，求出 $k$。

核心观察

1. 数组仅有一个 $1$，因此区间查询结果仅由两个因素决定：$1$ 的位置 $p$、区间长度是否 $\ge k$；
2. $n$ 是 $2$ 的幂，天然适合二分查找（查询次数 $\log_2(2^{30})=30 \le33$，完全满足限制）；
3. 我们可以通过分块查询，快速定位 $1$ 的大致位置，再二分精确求出 $k$。

解题思路

代码的核心逻辑分为 4 个步骤，全程利用 $n$ 是 $2$ 的幂的特性：

1. 四等分定位：将数组分为 4 个等大的块，查询前两个块，判断 $1$ 在左半部分还是右半部分；
2. 划分 $k$ 范围：查询长度为 $n/2$ 的区间，判断 $k$ 是小值（$\le n/2$）还是大值（$>n/2$）；
3. 二分精确求解：根据 $k$ 的范围，二分查找最小的 $k$（即查询结果发生翻转的临界长度）；
4. 输出答案：二分得到的结果即为隐藏的 $k$。

代码详解

原代码问题修复

原代码存在交互题致命bug，已在完整AC代码中修复：

1. 缺少输出刷新 flush（交互题必须每次查询后刷新缓冲区）；
2. $n\le2^{30}$，int 溢出，改用 long long；
3. 未处理返回值 $-1$（题目要求读到 $-1$ 立即退出）；
4. 变量名冲突、逻辑细节优化。

函数与变量解释

1. qry 函数：封装查询逻辑，支持区间翻转（适配 $1$ 在右半部分的情况）；
2. firstHalf：标记 $1$ 在数组左半部分（true）还是右半部分（false）；
3. kSmall：标记 $k$ 是小值（$\le n/2$）还是大值（$>n/2$）；
4. 二分查找：倍增式二分，快速缩小 $k$ 的范围。

完整AC代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

// 交互查询函数：l,r为0下标，rev=翻转标记，n=数组长度
ll qry(ll l, ll r, bool rev, ll n) {
    if (rev) {
        // 区间翻转：适配1在右半部分的情况
        ll t = n - l;
        l = n - r;
        r = t;
    }
    // 输出查询，转换为题目要求的1下标
    cout << "? " << l + 1 << " " << r << endl;
    // 强制刷新输出缓冲区（交互题必备）
    cout.flush();
    ll res;
    cin >> res;
    // 读到-1，程序立即退出（题目强制要求）
    if (res == -1) exit(0);
    return res;
}

void solve() {
    ll n;
    cin >> n;
    // 步骤1：查询前两个四等分块，判断1在左半/右半
    ll a = qry(0, n / 4, false, n);
    ll b = qry(n / 4, n / 2, false, n);
    bool firstHalf = true;
    if (a == b) firstHalf = false; // 1在右半部分

    // 步骤2：判断k是小值(<=n/2)还是大值(>n/2)
    bool kSmall = true;
    if (qry(0, n / 2, firstHalf, n) == 0) {
        kSmall = false;
    }

    ll bs = 0;
    // 步骤3：二分查找精确的k值
    if (kSmall) {
        // 情况1：k <= n/2，正向二分
        for (ll k = n / 4; k > 0; k /= 2) {
            if (qry(0, bs + k, firstHalf, n) == 0) {
                bs += k;
            }
        }
    } else {
        // 情况2：k > n/2，反向二分
        bs = n / 2 - 1;
        for (ll k = n / 4; k > 0; k /= 2) {
            if (qry(0, bs + k, !firstHalf, n) == 1) {
                bs += k;
            }
        }
    }

    // 输出答案
    cout << "! " << bs + 1 << endl;
    cout.flush();
}

int main() {
    // 关闭同步，加速输入输出
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}

复杂度分析

1. 时间复杂度：$\mathcal{O}(T\log n)$
   • 每组测试用例仅执行 $\log_2 n$ 次查询（最多 $30$ 次），远小于题目限制的 $33$ 次；
   • 测试用例数 $T\le500$，总查询数 $500\times30=15000$，完全合规。
2. 空间复杂度：$\mathcal{O}(1)$，仅使用常数变量。

正确性证明

1. 定位 $1$ 的位置：四等分查询可以无歧义判断 $1$ 在左/右半部分；
2. 划分 $k$ 范围：长度为 $n/2$ 的查询，能直接区分 $k\le n/2$ 和 $k>n/2$；
3. 二分求解：利用查询结果的翻转特性，二分可以精准找到临界长度 $k$；
4. 查询次数：$\log_2(2^{30})=30 \le33$，满足题目硬限制。

关键注意事项（交互题必看）

1. 每次输出后必须刷新缓冲区（cout.flush()），否则会触发超时；
2. 必须处理返回值 $-1$，读到后立即退出程序；
3. 数据类型用 long long，$n$ 最大为 $2^{30}$，int 会溢出；
4. 题目数组下标为 $1$，代码内部用 $0$ 下标更方便，查询时转换即可。