311354: CF1973D. Cat, Fox and Maximum Array Split

D. Cat, Fox and Maximum Array Splittime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

This is an interactive problem.

Fox gave Cat two positive integers $n$ and $k$. She has a hidden array $a_1, \ldots , a_n$ of length $n$, such that $1 \leq a_i \leq n$ for every $i$. Now they are going to play the following game:

For any two integers $l, r$ such that $1 \leq l \leq r \leq n$, define $f(l, r) = (r - l + 1) \cdot \max\limits_{x=l}^r a_x$. In other words, $f(l, r)$ is equal to the maximum of the subarray $a_l, \ldots, a_r$ multiplied by its size.

Cat can ask Fox at most $2 n$ questions about the array. He will tell her two integers $l$ and $x$ ($1 \leq l \leq n, 1 \leq x \leq 10^9$), and she will tell him one integer $p$ as the answer — the smallest positive integer $r$ such that $f(l, r) = x$, or $n+1$ if no such $r$ exists.

Now, Cat needs to find the largest value $m$ such that there exists a sequence $c_1, \ldots, c_{k-1}$ such that $1 \leq c_1 < \ldots < c_{k-1} < n$ and $f(1, c_1) = f(c_1 + 1, c_2) = \ldots = f(c_{k-1}+1, n) = m$. If no such $m$ exists, he should indicate this and take $-1$ as the answer. Note that for $k = 1$, $m$ is always equal to $f(1, n)$.

In other words, the goal is to find the largest $m$ such that you can split the array into exactly $k$ subarrays ($k$ is the constant given to you in the beginning of the interaction) so that all the subarrays have the product of their length and their maximum equal to $m$, or determine that no such $m$ exists. Every element should belong in exactly one of the subarrays.

Cat doesn't know what he should do, so he asked you to play the game for him.

Interaction

Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 10^3$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two positive integers $n$ and $k$ ($1 \leq k \leq n \leq 10^4$) — the length of the hidden array and the number of subarrays in the desired split.

Now you are allowed to make queries in the following way — print one line of the form "$\mathtt{?} \ l \ x$" (it must hold that $1 \leq l \leq n$, $1 \leq x \leq 10^9$) and you will receive the smallest integer $r$ such that $l \leq r \leq n$ and $f(l, r) = x$, or $n + 1$ if no such $r$ exists.

If you want to print the answer, output "$\mathtt{!} \ m$" and you will recieve $1$ if your answer is correct and $-1$ otherwise. In the first case, the interaction continues with the next test case. Note that printing the answer doesn't count towards the number of queries made. Please note that you don't receive the values for the next test case immediately, you will first have to read whether your answer to the last test case was correct.

If you receive the integer $-1$ at any moment, it means your program has made an invalid query, exceeded the query limit, or gave an incorrect answer. Your program must terminate immediately to receive a Wrong Answer verdict. Otherwise, you can get an arbitrary verdict because your solution will continue to read from a closed stream.

After printing a query, do not forget to output end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

• fflush(stdout) or cout.flush() in C++;
• System.out.flush() in Java;
• flush(output) in Pascal;
• stdout.flush() in Python;
• see documentation for other languages.

It is guaranteed that the total sum of $n$ over the test cases won't exceed $10^4$.

Hacks

The format of the hacks should be the following: the first line should contain one integer $t$ ($1 \leq t \leq 10^3$) — the number of test cases. The description of the test cases should follow.

The first line of each test case should contain two integers $n$ and $k$ ($1 \leq k \leq n \leq 10^4$) — the length of the array $a$ and the number of subarrays you want to split it into.

The second line should contain $n$ integers $a_1, a_2, \ldots, a_n $ ($1 \leq a_i \leq n $).

The sum of $n$ over all test cases should not exceed $10^4$.

ExampleInput

3
1 1

1
2 2

1

3

1
6 3

7

2

3

6

1

Output

! 1


? 1 1

? 2 1

! -1


? 1 9

? 1 6

? 3 6

? 4 6

! 6

Note

The hidden arrays in the three testcases are $[1]$, $[1, 2]$ and $[1, 3, 6, 1, 2, 1]$. In the second testcase, no split satisfies the constraints, so the answer is $-1$.

The answer for the first query of the third testcase is $7$ since no valid $r$ exists. For the second query of the third testcase, since $2 \cdot \max(1, 3) = 6$, we will get $2$ as the answer, since $r = 1$ doesn't satisfy the constraint.

The sample interaction guessed all three answers ($1, -1$ and $6$) correctly, so it received $1$ after each answer.

题目大意：

这是一个交互式问题。Fox给了Cat两个正整数n和k。她有一个隐藏的数组a_1, ..., a_n，长度为n，使得对于每个i，有1 ≤ a_i ≤ n。现在他们将玩以下游戏：

对于任意两个整数l, r，使得1 ≤ l ≤ r ≤ n，定义f(l, r) = (r - l + 1) * max_{x=l}^r a_x。换句话说，f(l, r)等于子数组a_l, ..., a_r的最大值乘以其大小。

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

现在，Cat需要找到最大的值m，使得存在一个序列c_1, ..., c_{k-1}，使得1 ≤ c_1 < ... < c_{k-1} < n且f(1, c_1) = f(c_1 + 1, c_2) = ... = f(c_{k-1}+1, n) = m。如果不存在这样的m，他应该指出这一点，并将-1作为答案。注意，对于k = 1，m总是等于f(1, n)。

换句话说，目标是要找到可以拆分数组为恰好k个子数组（k是在交互开始时给你的常数）的最大的m，使得所有子数组的长度和其最大值的乘积等于m，或者确定不存在这样的m。每个元素应该恰好属于一个子数组。

Cat不知道他应该做什么，所以他要求你替他玩游戏。

输入输出数据格式：

每个测试包含多个测试用例。第一行包含一个整数t（1 ≤ t ≤ 10^3）——测试用例的数量。接下来是测试用例的描述。

每个测试用例的第一行包含两个正整数n和k（1 ≤ k ≤ n ≤ 10^4）——隐藏数组的长度和期望拆分的子数组的数量。

现在你可以按照以下方式提出查询——打印一行形如" ? l x "的字符串（必须满足1 ≤ l ≤ n，1 ≤ x ≤ 10^9），然后你将收到满足l ≤ r ≤ n和f(l, r) = x的最小的整数r，或者如果不存在这样的r，则返回n + 1。

如果你要打印答案，输出" ! 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。

请注意，本题的交互性质要求你在解决问题时进行实际的查询和输出操作。题目大意： 这是一个交互式问题。Fox给了Cat两个正整数n和k。她有一个隐藏的数组a_1, ..., a_n，长度为n，使得对于每个i，有1 ≤ a_i ≤ n。现在他们将玩以下游戏： 对于任意两个整数l, r，使得1 ≤ l ≤ r ≤ n，定义f(l, r) = (r - l + 1) * max_{x=l}^r a_x。换句话说，f(l, r)等于子数组a_l, ..., a_r的最大值乘以其大小。 Cat可以最多询问Fox关于数组的2n个问题。他会告诉她两个整数l和x（1 ≤ l ≤ n, 1 ≤ x ≤ 10^9），她会告诉他一个整数p作为答案——满足f(l, r) = x的最小的正整数r，或者如果不存在这样的r，则返回n+1。 现在，Cat需要找到最大的值m，使得存在一个序列c_1, ..., c_{k-1}，使得1 ≤ c_1 < ... < c_{k-1} < n且f(1, c_1) = f(c_1 + 1, c_2) = ... = f(c_{k-1}+1, n) = m。如果不存在这样的m，他应该指出这一点，并将-1作为答案。注意，对于k = 1，m总是等于f(1, n)。 换句话说，目标是要找到可以拆分数组为恰好k个子数组（k是在交互开始时给你的常数）的最大的m，使得所有子数组的长度和其最大值的乘积等于m，或者确定不存在这样的m。每个元素应该恰好属于一个子数组。 Cat不知道他应该做什么，所以他要求你替他玩游戏。 输入输出数据格式： 每个测试包含多个测试用例。第一行包含一个整数t（1 ≤ t ≤ 10^3）——测试用例的数量。接下来是测试用例的描述。 每个测试用例的第一行包含两个正整数n和k（1 ≤ k ≤ n ≤ 10^4）——隐藏数组的长度和期望拆分的子数组的数量。 现在你可以按照以下方式提出查询——打印一行形如" ? l x "的字符串（必须满足1 ≤ l ≤ n，1 ≤ x ≤ 10^9），然后你将收到满足l ≤ r ≤ n和f(l, r) = x的最小的整数r，或者如果不存在这样的r，则返回n + 1。 如果你要打印答案，输出" ! 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。 请注意，本题的交互性质要求你在解决问题时进行实际的查询和输出操作。