CF1867E2 Salyg1n and Array (hard version)

这是该问题的困难版本。两个版本的唯一区别在于查询次数的限制。在本版本中，你最多只能进行 $57$ 次查询。只有当你同时解决了两个版本的问题后，才能进行 Hack。 这是一个交互题！ salyg1n 给了你一个正整数 $k$，并想和你玩一个游戏。他选择了一个长度为 $n$ 的整数数组 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 10^9$）。你需要输出 $a_1 \oplus a_2 \oplus \ldots \oplus a_n$，其中 $\oplus$ 表示[按位异或](https://en.wikipedia.org/wiki/Bitwise_operation#XOR)运算。你可以进行如下类型的查询： - $?$ $i$ ：对于该查询，你将收到 $a_i \oplus a_{i+1} \oplus \ldots \oplus a_{i+k-1}$ 的结果。同时，在该查询后，子数组 $a_i, a_{i+1}, \ldots, a_{i+k-1}$ 会被反转，即数组 $a$ 变为：$a_1, a_2, \ldots, a_{i-1}, a_{i+k-1}, a_{i+k-2}, \ldots, a_{i+1}, a_i, a_{i+k}, \ldots, a_n$。 你最多只能进行 $57$ 次查询来回答问题。

第一行包含一个整数 $t$（$1 \leq t \leq 1000$）——测试用例的数量。

你的程序与评测程序的交互从读取两个正的偶数 $n$ 和 $k$ 开始（$1 \leq k \leq n \leq k^2 \leq 2500$）——所选数组的长度和查询子数组的长度。 要获得 $a_i \oplus a_{i+1} \oplus \ldots \oplus a_{i+k-1}$ 的值，按格式输出查询 $?$ $i$（$1 \leq i \leq n-k+1$）。然后读取一个整数——你查询的答案。 你最多只能进行 $57$ 次查询。当你准备好输出答案时，按格式输出 $!$ $x$。之后，继续处理下一个测试用例，或者如果是最后一个测试用例则终止程序。输出答案不计入 $57$ 次查询。 如果你的程序对一组输入数据进行了超过 $57$ 次查询，或进行了无效查询，则该查询的响应将为 $-1$。收到该响应后，你的程序应立即终止以获得 Wrong Answer 判定。否则，可能会收到其他判定。 每次输出查询后不要忘记换行并刷新输出，否则会收到 Idleness limit exceeded 判定。为此，请使用： - C++：fflush(stdout) 或 cout.flush() - Java：System.out.flush() - Pascal：flush(output) - Python：stdout.flush() - 其他语言请查阅相关文档。 保证所有测试用例中 $n$ 的总和不超过 $10000$。本题的交互器是非自适应的。 Hack 格式： 要进行 Hack，请使用以下格式： 第一行包含一个整数 $t$——测试用例数量。 每个测试用例的描述由两行组成。第一行包含 $n$ 和 $k$——所选数组的长度和查询子数组的长度。第二行包含 $n$ 个数 $a_1, a_2, \ldots, a_n$——评测程序应选择的数组。

在第一个测试用例中，评测程序选择的数组为 $a = [4, 2, 5, 1]$。 在第二个测试用例中，评测程序选择的数组为 $a = [5, 7, 1, 3, 3, 7]$。 由 ChatGPT 4.1 翻译