A16671. Diadrash (Hard Version)
编程题
提高+/省选-
知识点
题目描述
这是本题的 Hard 版本。不同之处在于本题最多可以进行 $30$ 次询问。只有在你已解决所有版本的本题时才能进行 Hack。
本题为交互题。
有一个你未知的排列 $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$ 个区间中，能得到的最大的 $\operatorname{MEX}$ 值。形式化地说，你需要确定 $\max_{i=1}^q{\operatorname{MEX}([p_{l_i}, p_{l_i+1}, \ldots, p_{r_i}])}$ 的值。为此，你最多可以进行 $30$ 次以下形式的询问：
- 任选整数 $1 \le l \le r \le n$，你将会收到 $\operatorname{MEX}([p_l, p_{l+1}, \ldots, p_r])$ 的值。
$^{\ast}$ 排列是指 $0$ 到 $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$。
本题为交互题。
有一个你未知的排列 $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$ 个区间中，能得到的最大的 $\operatorname{MEX}$ 值。形式化地说，你需要确定 $\max_{i=1}^q{\operatorname{MEX}([p_{l_i}, p_{l_i+1}, \ldots, p_{r_i}])}$ 的值。为此，你最多可以进行 $30$ 次以下形式的询问：
- 任选整数 $1 \le l \le r \le n$，你将会收到 $\operatorname{MEX}([p_l, p_{l+1}, \ldots, p_r])$ 的值。
$^{\ast}$ 排列是指 $0$ 到 $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 \cdot 10^5$），分别表示排列的长度和区间数量。
接下来的 $q$ 行每行包含两个整数 $l_i, r_i$（$1 \le l_i \le r_i \le n$）。
保证所有测试用例中 $n$ 和 $q$ 的总和分别不超过 $10^4$ 和 $3 \cdot 10^5$。
额外约定：同一测试用例中没有重复的区间。
每组用例第一行包含两个正整数 $n$ 和 $q$（$4 \le n \le 10^4$，$1 \le q \le 3 \cdot 10^5$），分别表示排列的长度和区间数量。
接下来的 $q$ 行每行包含两个整数 $l_i, r_i$（$1 \le l_i \le r_i \le n$）。
保证所有测试用例中 $n$ 和 $q$ 的总和分别不超过 $10^4$ 和 $3 \cdot 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]$。第 $3$ 个区间最优，因为 $\operatorname{MEX}([p_1, p_2, p_3]) = \operatorname{MEX}([0, 3, 1]) = 2$，为最大值。
第一次询问我们查询 $l=1, r=3$，裁判返回 $\operatorname{MEX}([p_1, p_2, p_3]) = 2$。第二次询问 $l=4, r=4$，裁判返回 $\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]$。
注意，这只是对交互方式的说明，并未展示任何解题策略。
第一次询问我们查询 $l=1, r=3$，裁判返回 $\operatorname{MEX}([p_1, p_2, p_3]) = 2$。第二次询问 $l=4, r=4$，裁判返回 $\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]$。
注意，这只是对交互方式的说明，并未展示任何解题策略。