CF1856D More Wrong

这是一个交互题。 评测机隐藏了一个长度为 $n$ 的排列 $^\dagger$ $p$。 每次询问，你可以选择两个整数 $l$ 和 $r$（$1 \le l < r \le n$），并支付 $(r - l)^2$ 个金币。作为回应，你将获得子数组 $[p_l, p_{l + 1}, \ldots, p_r]$ 中的逆序对数 $^\ddagger$。 请在花费不超过 $5 \cdot n^2$ 个金币的前提下，找出 $p$ 中最大元素的位置。 注意：评测机不是自适应的，排列在所有询问之前就已经固定。 $^\dagger$ 长度为 $n$ 的排列是一个包含 $n$ 个互不相同的整数的数组，这些整数取自 $1$ 到 $n$，顺序任意。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是排列（$2$ 出现了两次），$[1,3,4]$ 也不是排列（$n=3$ 但出现了 $4$）。 $^\ddagger$ 一个数组的逆序对数是指满足 $i < j$ 且 $a_i > a_j$ 的下标对 $(i,j)$ 的数量。例如，数组 $[10,2,6,3]$ 有 $4$ 个逆序对，分别是 $(1,2),(1,3),(1,4)$ 和 $(3,4)$。

每个测试点包含多组测试数据。输入的第一行包含一个整数 $t$（$1 \le t \le 100$），表示测试用例的数量。 每个测试用例的唯一一行包含一个整数 $n$（$2 \le n \le 2000$），表示隐藏排列 $p$ 的长度。 保证所有测试用例中 $n$ 的总和不超过 $2000$。

每个测试用例的交互流程如下： 首先读取一个整数 $n$。 每次询问时，输出 "? l r"（$1 \le l < r \le n$，不含引号）。随后，你应读取一个整数——该询问的答案。 如果你收到 $-1$ 作为答案或 $n$ 的值，说明你的程序进行了非法询问、超出了询问次数限制，或在前一个测试用例中给出了错误答案。你的程序必须立即终止，否则会收到 Wrong Answer 判定。否则，如果继续读取关闭的流，你可能会得到任意判定。 当你准备给出最终答案时，输出 "! i"（$1 \le i \le n$，不含引号），表示隐藏排列中最大元素的位置。解决完一个测试用例后，立即进入下一个测试用例。所有测试用例结束后，程序应立即终止。 每次输出询问后不要忘记输出换行并刷新输出缓冲区，否则会收到 Idleness limit exceeded 判定。具体做法如下： - C++：fflush(stdout) 或 cout.flush() - Java：System.out.flush() - Pascal：flush(output) - Python：stdout.flush() - 其它语言请查阅相关文档。 Hack 格式 Hack 时请使用以下格式： 第一行包含一个整数 $t$（$1 \le t \le 100$），表示测试用例数量。 每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 2000$），表示隐藏排列 $p$ 的长度。 每个测试用例的第二行包含 $n$ 个整数 $p_1,p_2,\ldots, p_n$（$1 \le p_i \le n$），$p$ 必须是一个排列。 所有测试用例中 $n$ 的总和不超过 $2000$。

在第一个测试中，交互过程如下： | Solution | Jury | Explanation | |----------|------|-------------| | 2 | | 有 $2$ 个测试用例。 | | 4 | | 第一个测试用例，隐藏排列为 $[1,3,2,4]$，长度为 $4$。 | | ? 1 3 | 1 | 询问子数组 $[1,3,2]$ 的逆序对数，支付 $4$ 个金币，评测机回答 $1$。 | | ? 3 4 | 0 | 询问子数组 $[2,4]$ 的逆序对数，支付 $1$ 个金币，评测机回答 $0$。 | | ! 4 | | 程序判断 $p_4 = 4$，输出 $4$。答案正确，进入下一个测试用例。 | | 2 | | 第二个测试用例，隐藏排列为 $[2,1]$，长度为 $2$。 | | ? 1 2 | 1 | 询问子数组 $[2,1]$ 的逆序对数，支付 $1$ 个金币，评测机回答 $1$。 | | ! 1 | | 程序判断 $p_1 = 2$，输出 $1$。答案正确，所有测试用例结束，程序退出。 | 注意：示例输入输出中的换行仅为便于阅读，实际交互时不会出现。 由 ChatGPT 4.1 翻译