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$ 作为反馈，你的程序必须立即终止，这意味着你的查询有误或已犯下其他错误，未能及时退出可能导致随意判定。

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 500 $ ). The description of the test cases follows. The first line of each test case contains one positive integer $ n $ ( $ 4 \le n \le 2^{30} $ ) — the length of the hidden array. It is guaranteed that $ \mathbf{n} $ is a power of 2; that is, $ n = 2^m $ for some non-negative integer $ m $ . You can make queries in the following way — print one line of the form " $ \mathtt{?}\,l\,r $ " where $ 1 \le l \le r \le n $ . After that, read a single integer: $ 0 $ or $ 1 $ , as described in the statement. If you want to print the answer $ k $ , output " $ \mathtt{!}\,k $ ". Then, the interaction continues with the next test case. Printing the answer does not count towards the number of queries made. After printing each query do not forget to output the end of line and flush $ ^{\text{∗}} $ the output. Otherwise, you will get Idleness limit exceeded verdict. If, at any interaction step, you read $ -1 $ instead of valid data, your solution must exit immediately. This means that your solution will receive Wrong answer because of an invalid query or any other mistake. Failing to exit can result in an arbitrary verdict because your solution will continue to read from a closed stream. Hacks The format of the hacks should be the following: the first line should contain one integer $ t $ ( $ 1 \le t \le 100 $ ) — the number of test cases. The description of the test cases should follow. The first and only line of each test case should contain three integers $ n $ , $ p $ , and $ k $ ( $ 4 \le n \le 2^{30} $ , $ 1 \le p \le n $ , $ 2 \le k \le n - 1 $ ) — the length of the hidden array $ a $ , the position of the only 1 in $ a $ , and the hidden $ k $ . $ n $ must be a power of $ 2 $ . $ ^{\text{∗}} $ To flush, use: - fflush(stdout) or cout.flush() in C++; - sys.stdout.flush() in Python; - see the documentation for other languages.

在第一个测试用例中，给出隐藏整数 $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 自动生成**