CF1973D.Cat, Fox and Maximum Array Split

这是一个交互题。

Fox 给了 Cat 两个正整数 $n$ 和 $k$。她有一个长度为 $n$ 的隐藏数组 $a_1, \ldots, a_n$，其中每个 $a_i$ 满足 $1 \leq a_i \leq n$。现在他们要玩如下的游戏：

对于任意两个整数 $l, r$，满足 $1 \leq l \leq r \leq n$，定义 $f(l, r) = (r - l + 1) \cdot \max\limits_{x=l}^r a_x$。也就是说，$f(l, r)$ 等于子数组 $a_l, \ldots, a_r$ 的最大值乘以其长度。

Cat 最多可以向 Fox 询问 $2n$ 个关于数组的问题。他每次会告诉她两个整数 $l$ 和 $x$（$1 \leq l \leq n, 1 \leq x \leq 10^9$），她会告诉他一个整数 $p$ 作为答案——即最小的正整数 $r$，使得 $f(l, r) = x$，如果不存在这样的 $r$，则返回 $n+1$。

现在，Cat 需要找到最大的值 $m$，使得存在一个序列 $c_1, \ldots, c_{k-1}$，满足 $1 \leq c_1 < \ldots < c_{k-1} < n$，并且 $f(1, c_1) = f(c_1 + 1, c_2) = \ldots = f(c_{k-1}+1, n) = m$。如果不存在这样的 $m$，他应当输出 $-1$ 作为答案。注意，当 $k = 1$ 时，$m$ 总是等于 $f(1, n)$。

换句话说，目标是找到最大的 $m$，使得你可以将数组恰好划分为 $k$ 个子数组（$k$ 是交互开始时给定的常数），并且所有子数组的长度与其最大值的乘积都等于 $m$，或者判断不存在这样的 $m$。每个元素必须且只能属于一个子数组。

Cat 不知道该怎么做，所以他请你帮他玩这个游戏。

每个测试点包含多组测试数据。第一行包含一个整数 $t$（$1 \leq t \leq 10^3$），表示测试数据组数。每组测试数据描述如下。

每组测试数据的第一行包含两个正整数 $n$ 和 $k$（$1 \leq k \leq n \leq 10^4$），分别表示隐藏数组的长度和希望划分的子数组数。

现在你可以进行如下查询——输出一行形如“$\mathtt{?}\ l\ x$”（需满足 $1 \leq l \leq n$，$1 \leq x \leq 10^9$），你将收到最小的整数 $r$，满足 $l \leq r \leq n$ 且 $f(l, r) = x$，若不存在这样的 $r$，则返回 $n+1$。

如果你想输出答案，输出一行“$\mathtt{!}\ m$”，你将收到 $1$ 表示答案正确，$-1$ 表示答案错误。在第一种情况下，交互继续到下一个测试点。注意，输出答案不计入查询次数。请注意，在你输出答案后，不会立即收到下一组测试数据的输入，你需要先读取你上一个答案是否正确。

如果你在任何时候收到 $-1$，说明你的程序进行了非法查询、超出了查询次数限制，或者给出了错误答案。你的程序必须立即终止，否则会收到错误答案（Wrong Answer）判定。否则，你的程序会继续读取已关闭的输入流，可能得到任意判定。

每次输出查询后，不要忘记输出换行并刷新输出缓冲区，否则会收到“Idleness limit exceeded”判定。具体做法如下：

• C++：fflush(stdout) 或 cout.flush()
• Java：System.out.flush()
• Pascal：flush(output)
• Python：stdout.flush()
• 其它语言请查阅相关文档。

保证所有测试点中 $n$ 的总和不超过 $10^4$。

Hack 数据

Hack 数据格式如下：第一行包含一个整数 $t$（$1 \leq t \leq 10^3$），表示测试数据组数。每组测试数据描述如下。

每组测试数据的第一行包含两个整数 $n$ 和 $k$（$1 \leq k \leq n \leq 10^4$），分别表示数组 $a$ 的长度和希望划分的子数组数。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq n$）。

所有测试点中 $n$ 的总和不超过 $10^4$。

见输入格式描述。

三组测试数据中的隐藏数组分别为 $[1]$、$[1, 2]$ 和 $[1, 3, 6, 1, 2, 1]$。在第二组测试数据中，没有任何划分满足条件，因此答案为 $-1$。

第三组测试数据的第一次查询答案为 $7$，因为不存在满足条件的 $r$。第二次查询中，由于 $2 \cdot \max(1, 3) = 6$，所以答案为 $2$，因为 $r = 1$ 不满足条件。

样例交互中三组答案（$1, -1, 6$）均猜对，因此每次都收到了 $1$。

由 ChatGPT 4.1 翻译