CF1372F Omkar and Modes

Ray 丢失了他的数组，需要通过向 Omkar 提问来找回它。Omkar 愿意透露该数组具有以下性质： 1. 该数组有 $n$ 个元素（$1 \le n \le 2 \cdot 10^5$）。 2. 数组中每个元素 $a_i$ 都是满足 $1 \le a_i \le 10^9$ 的整数。 3. 该数组是非递减排序的。 Ray 可以向 Omkar 发送一系列查询。每次查询包含两个整数 $l$ 和 $r$，满足 $1 \le l \le r \le n$。Omkar 会回复两个整数 $x$ 和 $f$。$x$ 是下标从 $l$ 到 $r$（包含两端）子数组的众数。众数定义为出现次数最多的数。如果有多个数出现次数相同，则取最小的那个数作为众数。$f$ 是 $x$ 在所查询子数组中出现的次数。 该数组有 $k$ 个不同的元素（$1 \le k \le \min(25000, n)$）。但由于 Ray 的“罪孽”，Omkar 不会告诉 Ray $k$ 的值。Ray 最多可以发送 $4k$ 次查询。 请帮助 Ray 找回他丢失的数组。

输入的唯一一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示你需要找回的数组的长度。

交互从读取 $n$ 开始。 然后你可以进行如下格式的查询： - “$? \ l \ r$”（$1 \le l \le r \le n$），其中 $l$ 和 $r$ 是你希望查询的子数组的区间。 每次查询的回复格式为 “$x \ f$”，其中 $x$ 是子数组的众数，$f$ 是 $x$ 在子数组中出现的次数。 - $x$ 满足 $1 \leq x \leq 10^9$。 - $f$ 满足 $1 \leq f \leq r-l+1$。 - 如果你查询次数超过 $4k$ 次，或查询区间不合法，将会收到输出 “-1”。 - 如果你在收到 “-1” 后终止，将会得到 “Wrong answer” 的判定。否则你的程序会因为继续读取已关闭的流而得到任意判定。 当你准备输出答案时，打印： - “$! \ a_1 \ a_2 \ \ldots \ a_{n-1} \ a_n$”，即感叹号后跟数组的所有元素，每个元素之间用空格隔开。 输出答案后请立即退出。该操作不计入 $4k$ 次查询限制。 每次输出查询后不要忘记输出换行并刷新输出流。否则会因“Idleness limit exceeded”而判错。具体操作如下： - C++：fflush(stdout) 或 cout.flush() - Java：System.out.flush() - Pascal：flush(output) - Python：stdout.flush() - 其它语言请查阅相关文档。 Hack 格式 进行 Hack 时，第一行输出一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）。第二行输出 $n$ 个整数 $a_1, a_2, \ldots, a_{n-1}, a_n$，用空格隔开，要求不同数字不超过 $25000$ 个，且 $a_j \le a_{j+1}$ 对所有 $j$ 成立（$1 \le j \le n-1$）。

第一次查询为 $l=1$，$r=6$。众数为 $2$，$2$ 出现了 $2$ 次，因此 $x=2$，$f=2$。注意 $3$ 也出现了两次，但因为 $2$ 更小，所以输出 $2$。 第二次查询为 $l=1$，$r=3$。众数为 $2$，$2$ 在区间 $[1,3]$ 中出现了两次。 第三次查询为 $l=4$，$r=6$。众数为 $3$，$3$ 在区间 $[4,6]$ 中出现了两次。 第四次查询为 $l=3$，$r=4$。众数为 $2$，在区间 $[3,4]$ 中出现了一次。注意 $3$ 也出现了一次，但 $2$ 更小。 由 ChatGPT 4.1 翻译