CF1584D Guess the Permutation

这是一个交互题。 评测系统最初有一个长度为 $n$ 的序列 $a$，其中 $a_i = i$。 评测系统选择了三个整数 $i$、$j$、$k$，满足 $1 \leq i < j < k \leq n$，且 $j - i > 1$。之后，评测系统将序列 $a$ 的两个子区间 $[i, j-1]$ 和 $[j, k]$ 进行了反转操作。 反转子区间 $[l, r]$ 指的是将区间 $a_l, a_{l+1}, \ldots, a_r$ 的元素顺序颠倒，即 $a_l$ 与 $a_r$ 交换，$a_{l+1}$ 与 $a_{r-1}$ 交换，依此类推。 现在给定数字 $n$，你需要通过提问若干次，找出被选中的 $i$、$j$、$k$。 每次提问，你可以选择两个整数 $l$ 和 $r$（$1 \leq l \leq r \leq n$），询问序列 $a$ 的子区间 $[l, r]$ 中的逆序对数量。你将得到区间 $[l, r]$ 内满足 $l \leq p < q \leq r$ 且 $a_p > a_q$ 的有序对 $(p, q)$ 的数量。 请在最多 $40$ 次提问内，找出被选中的 $i$、$j$、$k$。 在你的程序开始前，$i$、$j$、$k$ 已经被固定，不会随着你的提问而改变。

每组测试数据包含多个测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 100$），表示测试用例的数量。每个测试用例描述如下： 每个测试用例的一行包含一个整数 $n$（$4 \leq n \leq 10^9$）。读入后，你应开始与评测系统进行交互，针对该测试用例进行提问。每次得到答案后： - 如果这是最后一个测试用例，程序应终止。 - 否则，继续处理下一个测试用例。

每次询问子区间 $[l, r]$ 的逆序对数量时，输出 "? l r"，其中 $1 \leq l \leq r \leq n$。每个测试用例最多可以询问 $40$ 次。每次询问后，你需要读入一个整数 $x$。 - 如果 $x = -1$，说明你的提问无效或已超过本测试用例的提问次数，程序应立即终止（否则可能会得到“Wrong Answer”判定）。 - 否则，$x$ 表示当前序列 $a$ 的子区间 $[l, r]$ 内的逆序对数量。 当你确定了答案后，输出 "! i j k"，其中 $i$、$j$、$k$ 是你找到的答案。然后继续处理下一个测试用例，或在最后一个测试用例后终止程序。 每次输出提问或答案后，别忘了输出换行并刷新输出缓冲区。否则会得到“Idleness limit exceeded”判定。具体做法如下： - C++：fflush(stdout) 或 cout.flush() - Java：System.out.flush() - Pascal：flush(output) - Python：stdout.flush() - 其它语言请查阅相关文档。 Hack 格式 如需制作 Hack，格式如下： 第一行一个整数 $t$（$1 \leq t \leq 100$），表示测试用例数量。 接下来 $t$ 行，每行四个整数 $n$、$i$、$j$、$k$（$4 \leq n \leq 10^9$，$1 \leq i < j < k \leq n$，$j - i > 1$）。

在第一个测试用例中，$i = 1$，$j = 3$，$k = 5$，所以序列 $a$ 为 $[2, 1, 5, 4, 3]$。 在第二个测试用例中，$i = 2$，$j = 4$，$k = 5$，所以序列 $a$ 为 $[1, 3, 2, 5, 4]$。 由 ChatGPT 4.1 翻译