CF1698D Fixed Point Guessing

这是一个交互题。 初始时，有一个数组 $a = [1, 2, \ldots, n]$，其中 $n$ 是一个奇数正整数。评测器选取了 $\frac{n-1}{2}$ 对不相交的元素对，然后将这些元素对中的元素进行交换。例如，如果 $a=[1,2,3,4,5]$，并且交换了 $1 \leftrightarrow 4$ 和 $3 \leftrightarrow 5$ 这两对元素，那么最终数组为 $[4, 2, 5, 1, 3]$。 经过这些交换后，恰好有一个元素的位置没有发生变化。你需要找出这个没有移动位置的元素。 为此，你可以进行若干次查询。每次查询，你可以选择两个整数 $l$ 和 $r$（$1 \leq l \leq r \leq n$）。作为回应，你将获得子数组 $[a_l, a_{l + 1}, \dots, a_r]$ 按升序排列后的结果。 请找出那个没有移动位置的元素。 你最多可以进行 $\mathbf{15}$ 次查询。 数组 $a$ 在交互开始前就已经确定，并且在你的查询过程中不会发生变化。 注意：如果数组 $b$ 是数组 $a$ 的一个子数组，那么 $b$ 可以通过从 $a$ 的开头和结尾各删除若干（可能为零）元素得到。

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 500$）——表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 $n$（$3 \leq n < 10^4$，$n$ 为奇数）——数组 $a$ 的长度。 读入每个测试用例的第一行后，你应当开始与评测器进行交互。 保证所有测试用例中 $n$ 的总和不超过 $10^4$。

对于每个测试用例，先读入整数 $n$。 每进行一次查询，输出一行 "$\texttt{?}\;l\;r$"（$1 \leq l \leq r \leq n$），不包含引号。随后，你应当读入 $r-l+1$ 个整数——即 $a_l, a_{l + 1}, \dots, a_r$ 按升序排列后的结果。每个测试用例最多允许进行 $15$ 次这样的查询。 如果你收到 $-1$ 作为答案或 $n$，这表示你的程序进行了非法查询、超出了查询次数限制，或在前一个测试用例中给出了错误答案。你的程序必须立即终止，否则会收到 Wrong Answer 判定。否则，如果你的程序继续从已关闭的流中读取数据，可能会得到任意判定。 当你准备给出最终答案时，输出一行 "$\texttt{!}\;x$"（$1 \leq x \leq n$），不包含引号——表示没有移动位置的元素。给出最终答案不计入 $15$ 次查询限制。之后，你的程序应继续解决剩余的测试用例，或在全部测试用例结束后退出。 每次输出查询后不要忘记换行并刷新输出缓冲区，否则会收到 Idleness limit exceeded 判定。具体做法如下： - C++：使用 fflush(stdout) 或 cout.flush() - Java：使用 System.out.flush() - Pascal：使用 flush(output) - Python：使用 stdout.flush() - 其它语言请查阅相关文档。 Hacks 制作 Hack 时，使用如下格式。第一行包含一个整数 $t$（$1 \leq t \leq 500$）——表示测试用例数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 $n$（$3 \leq n < 10^4$，$n$ 为奇数）——数组 $a$ 的长度。 第二行包含 $n$ 个用空格分隔的整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le n$）——数组 $a$。该数组应当是对 $[1,2,\dots,n]$ 经过 $\frac{n-1}{2}$ 对不相交元素交换后得到的结果。

在第一个测试中，交互过程如下： SolutionJuryExplanation $\texttt{2}$ 有 $2$ 个测试用例。 $\texttt{5}$ 在第一个测试用例中，隐藏数组为 $[4,2,5,1,3]$，长度为 $5$。 $\texttt{? 1 4}$ $\texttt{1 2 4 5}$ 选手请求了子数组 $[4,2,5,1]$，评测器返回 $[1,2,4,5]$。 $\texttt{? 3 5}$ $\texttt{1 3 5}$ 选手请求了子数组 $[5,1,3]$，评测器返回 $[1,3,5]$。 $\texttt{! 2}$ 选手判断 $a_2=2$，并输出。答案正确，进入下一个测试用例。 $\texttt{3}$ 在第二个测试用例中，隐藏数组为 $[1,3,2]$，长度为 $3$。 $\texttt{? 1 1}$ $\texttt{1}$ 选手请求了 $[1]$，评测器返回 $[1]$。 $\texttt{! 1}$ 选手判断 $a_1=1$，并输出。答案正确，全部测试用例结束，交互终止。 注意：示例输入输出中的换行仅为便于阅读，实际交互中不会出现。 由 ChatGPT 4.1 翻译