Fixed Point Guessing

题意翻译

**本题为交互题且有多组数据，请注意清空缓冲区。** 有一个长度为 $n$ 的数组（$n$ 为奇数）。一开始满足 $a_i=i$ 。接下来进行了 $\frac{n-1}{2}$ 次交换，每次将数组中的任意两个数交换位置，且每个数被交换**至多一次**。 你可以以 ```? l r``` 的格式发起询问，然后交互库会返回以升序返回给你区间 $[l,r]$ 之间的所有数。你需要**在 $15$ 次操作以内**，找到没有被交换过的数，并以 ```! x``` 的格式输出。 $1\leq T\leq 500,3\leq \sum n<10^4$

题目描述

This is an interactive problem. Initially, there is an array $ a = [1, 2, \ldots, n] $ , where $ n $ is an odd positive integer. The jury has selected $ \frac{n-1}{2} $ disjoint pairs of elements, and then the elements in those pairs are swapped. For example, if $ a=[1,2,3,4,5] $ , and the pairs $ 1 \leftrightarrow 4 $ and $ 3 \leftrightarrow 5 $ are swapped, then the resulting array is $ [4, 2, 5, 1, 3] $ . As a result of these swaps, exactly one element will not change position. You need to find this element. To do this, you can ask several queries. In each query, you can pick two integers $ l $ and $ r $ ( $ 1 \leq l \leq r \leq n $ ). In return, you will be given the elements of the subarray $ [a_l, a_{l + 1}, \dots, a_r] $ sorted in increasing order. Find the element which did not change position. You can make at most $ \mathbf{15} $ queries. The array $ a $ is fixed before the interaction and does not change after your queries. Recall that an array $ b $ is a subarray of the array $ a $ if $ b $ can be obtained from $ a $ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

输入输出格式

输入格式

Each test contains multiple test cases. The first line contains an integer $ t $ ( $ 1 \leq t \leq 500 $ ) — the number of test cases. The description of the test cases follows. The first line of each test case contains an integer $ n $ ( $ 3 \leq n < 10^4 $ ; $ n $ is odd) — the length of the array $ a $ . After reading the first line of each test case, you should begin the interaction. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^4 $ .

输出格式

For each test case, begin the interaction by reading the integer $ n $ . To make a query, output " $ \texttt{?}\;l\;r $ " ( $ 1 \leq l \leq r \leq n $ ) without quotes. Afterwards, you should read in $ r-l+1 $ integers — the integers $ a_l, a_{l + 1}, \dots, a_r $ , in increasing order. You can make at most $ 15 $ such queries in a single test case. If you receive the integer $ -1 $ instead of an answer or the integer $ n $ , it means your program has made an invalid query, has exceed the limit of queries, or has given incorrect answer on the previous test case. 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. When you are ready to give the final answer, output " $ \texttt{!}\;x $ " ( $ 1 \leq x \leq n $ ) without quotes — the element that did not change position. Giving this answer does not count towards the limit of $ 15 $ queries. Afterwards, your program must continue to solve the remaining test cases, or exit if all test cases have been solved. 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. Hacks To make a hack, use the following format. The first line must contain an integer $ t $ ( $ 1 \leq t \leq 500 $ ) — the number of test cases. The description of the test cases follows. The first line of each test case must contain an integer $ n $ ( $ 3 \leq n < 10^4 $ ; $ n $ is odd) — the length of the array $ a $ . The second line of each test case must contain $ n $ space-separated integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le n $ ) — the elements of $ a $ . The array $ a $ should be the result of $ \frac{n-1}{2} $ disjoint swaps on the array $ [1,2,\dots,n] $ .

输入输出样例

输入样例 #1

2
5

1 2 4 5

1 3 5

3

1

输出样例 #1

? 1 4

? 3 5

! 2

? 1 1

! 1

说明

In the first test, the interaction proceeds as follows. SolutionJuryExplanation $ \texttt{2} $ There are 2 test cases. $ \texttt{5} $ In the first test case, the hidden array is $ [4,2,5,1,3] $ , with length $ 5 $ . $ \texttt{? 1 4} $ $ \texttt{1 2 4 5} $ The solution requests the subarray $ [4,2,5,1] $ in increasing order, and the jury responds with $ [1,2,4,5] $ . $ \texttt{? 3 5} $ $ \texttt{1 3 5} $ The solution requests the subarray $ [5,1,3] $ in increasing order, and the jury responds with $ [1,3,5] $ . $ \texttt{! 2} $ The solution has somehow determined that $ a_2=2 $ , and outputs it. Since the output is correct, the jury continues to the next test case. $ \texttt{3} $ In the second test case, the hidden array is $ [1,3,2] $ , with length $ 3 $ . $ \texttt{? 1 1} $ $ \texttt{1} $ The solution requests the number $ [1] $ only, and the jury responds with $ [1] $ . $ \texttt{! 1} $ The solution has determined that $ a_1=1 $ , and outputs it. Since the output is correct and there are no more test cases, the jury and the solution exit.Note that the line breaks in the example input and output are for the sake of clarity, and do not occur in the real interaction.

**固定点猜测**

**题意翻译**
- 本题为交互题且有多组数据，请注意清空缓冲区。
- 有一个长度为 $ n $ 的数组（$ n $ 为奇数）。一开始满足 $ a_i=i $ 。接下来进行了 $ \frac{n-1}{2} $ 次交换，每次将数组中的任意两个数交换位置，且每个数被交换**至多一次**。
- 你可以以 ```? l r``` 的格式发起询问，然后交互库会返回以升序返回给你区间 $[l,r]$ 之间的所有数。你需要**在 15 次操作以内**，找到没有被交换过的数，并以 ```! x``` 的格式输出。
- $ 1 \leq T \leq 500, 3 \leq \sum n < 10^4 $

**题目描述**
- 这是一个交互问题。
- 初始时有一个数组 $ a = [1, 2, \ldots, n] $ ，其中 $ n $ 是一个奇数正整数。裁判选择了 $ \frac{n-1}{2} $ 个不相交的元素对，然后交换这些对中的元素。例如，如果 $ a=[1,2,3,4,5] $ ，并且交换了 $ 1 \leftrightarrow 4 $ 和 $ 3 \leftrightarrow 5 $ 对，则结果数组是 $ [4, 2, 5, 1, 3] $ 。
- 作为这些交换的结果，正好有一个元素位置不会改变。你需要找到这个元素。
- 为了做到这一点，你可以进行几次查询。每次查询，你可以选择两个整数 $ l $ 和 $ r $ （ $ 1 \leq l \leq r \leq n $ ）。作为回报，你将得到子数组 $ [a_l, a_{l + 1}, \dots, a_r] $ 按升序排列的元素。
- 找到没有改变位置的元素。你最多可以进行 15 次查询。
- 数组 $ a $ 在交互之前是固定的，并且在你查询之后不会改变。

**输入输出格式**
- 输入格式：每个测试用例包含多个测试案例。第一行包含一个整数 $ t $ （ $ 1 \leq t \leq 500 $ ）——测试案例的数量。测试案例的描述随之而来。
- 每个测试案例的第一行包含一个整数 $ n $ （ $ 3 \leq n < 10^4 $ ；$ n $ 是奇数）——数组 $ a $ 的长度。
- 输出格式：对于每个测试案例，开始交互并读取整数 $ n $ 。
- 要发起查询，输出 `` $ \texttt{?}\;l\;r $ `` （ $ 1 \leq l \leq r \leq n $ ）不加引号。之后，你应该读取 $ r-l+1 $ 个整数——整数 $ a_l, a_{l + 1}, \dots, a_r $ ，按升序排列。你可以在单个测试案例中最多进行 15 次这样的查询。
- 如果你的程序收到整数 $ -1 $ 而不是答案，或者超过了查询限制，或者在上一个测试案例中给出了错误的答案，你的程序必须立即终止以获得错误的答案。否则你可能会得到任意的裁决，因为你的解决方案会继续从已关闭的流中读取。
- 当你准备好给出最终答案时，输出 `` $ \texttt{!}\;x $ `` （ $ 1 \leq x \leq n $ ）不加引号——没有改变位置的元素。给出这个答案不计入 15 次查询的限制。之后，你的程序必须继续解决剩余的测试案例，或者在解决所有测试案例后退出。

**输入输出样例**
- 输入样例 #1
```
2
5
1 2 4 5
1 3 5
3
1
```
- 输出样例 #1
```
? 1 4
? 3 5
! 2
? 1 1
! 1
```**固定点猜测** **题意翻译** - 本题为交互题且有多组数据，请注意清空缓冲区。 - 有一个长度为 $ n $ 的数组（$ n $ 为奇数）。一开始满足 $ a_i=i $ 。接下来进行了 $ \frac{n-1}{2} $ 次交换，每次将数组中的任意两个数交换位置，且每个数被交换**至多一次**。 - 你可以以 ```? l r``` 的格式发起询问，然后交互库会返回以升序返回给你区间 $[l,r]$ 之间的所有数。你需要**在 15 次操作以内**，找到没有被交换过的数，并以 ```! x``` 的格式输出。 - $ 1 \leq T \leq 500, 3 \leq \sum n < 10^4 $ **题目描述** - 这是一个交互问题。 - 初始时有一个数组 $ a = [1, 2, \ldots, n] $ ，其中 $ n $ 是一个奇数正整数。裁判选择了 $ \frac{n-1}{2} $ 个不相交的元素对，然后交换这些对中的元素。例如，如果 $ a=[1,2,3,4,5] $ ，并且交换了 $ 1 \leftrightarrow 4 $ 和 $ 3 \leftrightarrow 5 $ 对，则结果数组是 $ [4, 2, 5, 1, 3] $ 。 - 作为这些交换的结果，正好有一个元素位置不会改变。你需要找到这个元素。 - 为了做到这一点，你可以进行几次查询。每次查询，你可以选择两个整数 $ l $ 和 $ r $ （ $ 1 \leq l \leq r \leq n $ ）。作为回报，你将得到子数组 $ [a_l, a_{l + 1}, \dots, a_r] $ 按升序排列的元素。 - 找到没有改变位置的元素。你最多可以进行 15 次查询。 - 数组 $ a $ 在交互之前是固定的，并且在你查询之后不会改变。 **输入输出格式** - 输入格式：每个测试用例包含多个测试案例。第一行包含一个整数 $ t $ （ $ 1 \leq t \leq 500 $ ）——测试案例的数量。测试案例的描述随之而来。 - 每个测试案例的第一行包含一个整数 $ n $ （ $ 3 \leq n < 10^4 $ ；$ n $ 是奇数）——数组 $ a $ 的长度。 - 输出格式：对于每个测试案例，开始交互并读取整数 $ n $ 。 - 要发起查询，输出 `` $ \texttt{?}\;l\;r $ `` （ $ 1 \leq l \leq r \leq n $ ）不加引号。之后，你应该读取 $ r-l+1 $ 个整数——整数 $ a_l, a_{l + 1}, \dots, a_r $ ，按升序排列。你可以在单个测试案例中最多进行 15 次这样的查询。 - 如果你的程序收到整数 $ -1 $ 而不是答案，或者超过了查询限制，或者在上一个测试案例中给出了错误的答案，你的程序必须立即终止以获得错误的答案。否则你可能会得到任意的裁决，因为你的解决方案会继续从已关闭的流中读取。 - 当你准备好给出最终答案时，输出 `` $ \texttt{!}\;x $ `` （ $ 1 \leq x \leq n $ ）不加引号——没有改变位置的元素。给出这个答案不计入 15 次查询的限制。之后，你的程序必须继续解决剩余的测试案例，或者在解决所有测试案例后退出。 **输入输出样例** - 输入样例 #1 ``` 2 5 1 2 4 5 1 3 5 3 1 ``` - 输出样例 #1 ``` ? 1 4 ? 3 5 ! 2 ? 1 1 ! 1 ```