A16670. Diadrash (Easy Version)
编程题
普及+/提高
知识点
题目描述
这是该问题的简单版本。本版本与其他版本的区别在于，你最多可以进行 $ \max(300, \lceil\frac{n}{2}\rceil+2) $ 次查询。只有当你解决了所有版本后，才可以进行 Hack。
本题为交互式题目。
有一个长度为 $n$ 的排列 $p$（从 $0$ 到 $n-1$ 的一个排列）对你隐藏。同时，给定 $q$ 个区间 $[l_1, r_1], [l_2, r_2], \ldots, [l_q, r_q]$，其中 $1 \le l_i \le r_i \le n$。
你需要找出在输入给定的 $q$ 个区间中，$p$ 对应的子序列的最大 $\operatorname{MEX}$。形式化地，你需要找出 $ \max_{i=1}^q \{\operatorname{MEX}([p_{l_i}, p_{l_i+1}, \ldots, p_{r_i}])\} $ 的值。为此，你最多可以进行 $ \max(300, \lceil\frac{n}{2}\rceil+2) $ 次如下类型的询问：
- 任选任意两个整数 $1 \le l \le r \le n$，你会得到 $\operatorname{MEX}([p_l, p_{l+1}, \ldots, p_r])$ 的值。
$^*$ 长度为 $n$ 的排列是 $[0, 1, \ldots, n-1]$ 的一个重新排列，使得每个数仅出现一次。例如，序列 $[0, 3, 1, 2]$ 是一个排列，而 $[0, 0, 2, 1]$ 不是。
$^\dagger$ $\operatorname{MEX}$ 指的是序列中未出现的最小非负整数。例如，$\operatorname{MEX}([0, 0, 1, 3]) = 2$，$\operatorname{MEX}([1, 2, 2]) = 0$。
本题为交互式题目。
有一个长度为 $n$ 的排列 $p$（从 $0$ 到 $n-1$ 的一个排列）对你隐藏。同时，给定 $q$ 个区间 $[l_1, r_1], [l_2, r_2], \ldots, [l_q, r_q]$，其中 $1 \le l_i \le r_i \le n$。
你需要找出在输入给定的 $q$ 个区间中，$p$ 对应的子序列的最大 $\operatorname{MEX}$。形式化地，你需要找出 $ \max_{i=1}^q \{\operatorname{MEX}([p_{l_i}, p_{l_i+1}, \ldots, p_{r_i}])\} $ 的值。为此，你最多可以进行 $ \max(300, \lceil\frac{n}{2}\rceil+2) $ 次如下类型的询问：
- 任选任意两个整数 $1 \le l \le r \le n$，你会得到 $\operatorname{MEX}([p_l, p_{l+1}, \ldots, p_r])$ 的值。
$^*$ 长度为 $n$ 的排列是 $[0, 1, \ldots, n-1]$ 的一个重新排列，使得每个数仅出现一次。例如，序列 $[0, 3, 1, 2]$ 是一个排列，而 $[0, 0, 2, 1]$ 不是。
$^\dagger$ $\operatorname{MEX}$ 指的是序列中未出现的最小非负整数。例如，$\operatorname{MEX}([0, 0, 1, 3]) = 2$，$\operatorname{MEX}([1, 2, 2]) = 0$。
输入格式
每组测试数据包含多组用例。第一行包含一个整数 $t$（$1 \le t \le 100$），表示测试用例组数。
每组测试数据的第一行包含两个整数 $n$ 和 $q$（$4 \le n \le 10^4$，$1 \le q \le 3 \times 10^5$），分别表示排列的长度和区间的数量。
接下来的 $q$ 行，每行包含两个整数 $l_i, r_i$（$1 \le l_i \le r_i \le n$）。
保证所有测试用例中 $n$ 之和不超过 $10^4$，$q$ 之和不超过 $3 \times 10^5$。
额外约束：同一组测试数据内没有重复的区间。
每组测试数据的第一行包含两个整数 $n$ 和 $q$（$4 \le n \le 10^4$，$1 \le q \le 3 \times 10^5$），分别表示排列的长度和区间的数量。
接下来的 $q$ 行，每行包含两个整数 $l_i, r_i$（$1 \le l_i \le r_i \le n$）。
保证所有测试用例中 $n$ 之和不超过 $10^4$，$q$ 之和不超过 $3 \times 10^5$。
额外约束：同一组测试数据内没有重复的区间。
输入输出样例
输入 #1
3 4 3 1 2 2 4 1 3 2 0 1 4 6 6 1 2 2 4 3 3 4 6 5 5 6 6 6 1 2 4 4 1 1 2 2 3 3 4 4
输出 #1
? 1 3 ? 4 4 ? 1 1 ? 1 4 ! 2 ? 1 6 ? 3 3 ? 2 4 ! 2 ! 1
说明/提示
在第一个样例中，隐藏的排列是 $p=[0,3,1,2]$，区间为 $[1,2]$，$[2,4]$，$[1,3]$。第三个区间是最优的，因为 $\operatorname{MEX}([p_1, p_2, p_3]) = \operatorname{MEX}([0, 3, 1]) = 2$，这是最大值。
在第一次查询中，询问 $l=1, r=3$，Judge 返回 $\operatorname{MEX}([p_1, p_2, p_3])=2$。第二次查询，询问 $l=4, r=4$，Judge 返回 $\operatorname{MEX}([p_4])=0$。类似地，$\operatorname{MEX}([p_1])=1$，$\operatorname{MEX}([p_1, p_2, p_3, p_4])=4$。
通过推理可以得知答案是 $2$。
在第二个样例中，$p=[3,5,0,1,4,2]$。
在第三个样例中，$p=[0,1,2,3]$。
请注意，这些只是交互方式的解释，并未展现任何解题策略。
由 ChatGPT 5 翻译
在第一次查询中，询问 $l=1, r=3$，Judge 返回 $\operatorname{MEX}([p_1, p_2, p_3])=2$。第二次查询，询问 $l=4, r=4$，Judge 返回 $\operatorname{MEX}([p_4])=0$。类似地，$\operatorname{MEX}([p_1])=1$，$\operatorname{MEX}([p_1, p_2, p_3, p_4])=4$。
通过推理可以得知答案是 $2$。
在第二个样例中，$p=[3,5,0,1,4,2]$。
在第三个样例中，$p=[0,1,2,3]$。
请注意，这些只是交互方式的解释，并未展现任何解题策略。
由 ChatGPT 5 翻译