CF2049E.Broken Queries

你是一位魔法师，你的作品被一条龙摧毁了，于是你决心用一台神奇的范围追踪器来追捕这条龙。然而，那条龙似乎在捉弄你。

这是一个交互式问题。

有一个隐藏的二进制数组 $a$，长度为 $n$（$n$ 是 $2$ 的幂），以及一个隐藏的整数 $k$（$2 \le k \le n - 1$）。数组 $a$ 中仅有一个元素是 $1$，其余元素都是 $0$。对于两个整数 $l$ 和 $r$（$1 \le l \le r \le n$），定义区间和为 $s(l, r) = a_l + a_{l+1} + \cdots + a_r$。

你持有一个魔法装置，它能接收区间并返回区间和，但如果区间的长度至少是 $k$，则装置返回结果的相反值。具体来说，每次你可以提交一对整数 $[l, r]$ 进行查询（$1 \le l \le r \le n$），装置会按照下述规则返回 $0$ 或 $1$：

• 如果 $r - l + 1 < k$，则返回 $s(l, r)$ 的实际值。
• 如果 $r - l + 1 \ge k$，则返回 $1 - s(l, r)$。

你需要用不超过 $33$ 次查询找到隐藏的 $k$。

请注意，这个装置对于不同的测试用例始终固定不变，即隐藏的数组 $a$ 和整数 $k$ 在游戏开始前就已经确定，并在整个过程中不变。

每个测试包含多个测试用例。第一行输入一个整数 $t$（$1 \le t \le 500$）表示测试用例的数量。接下来就是每个测试用例的详细描述。

每个测试用例的第一行包含一个正整数 $n$（$4 \le n \le 2^{30}$），表示隐藏数组的长度。保证 $n$ 是 $2$ 的幂，即 $n = 2^m$，这里 $m$ 是非负整数。

你可以通过输出一行形如 “? l r” 的指令进行查询，这里的 $1 \le l \le r \le n$。之后，你会读取一个整数：$0$ 或 $1$，来获取结果。

如果要输出答案 $k$，则请输出 “! k”。输出答案后，程序将进入下一个测试用例。

每次输出查询时，请确保在最后输出换行符并刷新输出，否则可能会因此超时。

如果在任何一步中收到 $-1$ 作为反馈，你的程序必须立即终止，这意味着你的查询有误或已犯下其他错误，未能及时退出可能导致随意判定。

null

在第一个测试用例中，给出隐藏整数 $k = 6$ 且数组中唯一的 $1$ 位于索引 $6$ 上，因此数组 $a = [0, 0, 0, 0, 0, 1, 0, 0]$。

• 对于查询 $(3, 5)$，因为 $5 - 3 + 1 = 3 < k$，装置返回实际结果。因为 $6$ 不在区间 $[3, 5]$ 内，返回 $0$。
• 对于查询 $(1, 8)$，因为 $8 - 1 + 1 = 8 \ge k$，装置返回相反结果，返回 $0$。
• 对于查询 $(4, 8)$，因为 $8 - 4 + 1 = 5 < k$，装置返回实际结果，返回 $1$。
• 对于查询 $(3, 8)$，因为 $8 - 3 + 1 = 6 \ge k$，装置返回相反结果，返回 $0$。

示例解决方案输出 $k=6$，这也是正确的答案。

在第二个测试用例中，$k = 2$，数组中的 $1$ 位于索引 $3$，因此 $a = [0, 0, 1, 0]$。

注意，示例解决方案在某些情况下可能无法充分确定 $k$，这仅仅是作为示例来提供参考。

本翻译由 AI 自动生成