[[二分]]

D2. Diadrash (Hard Version)

时间限制：每点 3 秒 内存限制：256 MB

问题描述

这是本题的困难版本。两个版本的区别在于，在此版本中你最多可以进行 30 次询问。仅当您解决了此问题的所有版本时，才能进行黑客攻击。

这是一个交互题。

存在一个长度为 $n$ 的排列 $p$，其元素为 $0$ 到 $n-1$ 的整数，它对您隐藏。此外，您会得到 $q$ 个区间 $[l_1,r_1],[l_2,r_2],\ldots,[l_q,r_q]$，其中 $1 \leq l_i \leq r_i \leq n$。

您需要找出在输入给出的这 $q$ 个区间对应的 $p$ 的值中，最大的 MEX 值。形式上，您必须找出 $\max_{i=1}^{q} \text{MEX}([p_{l_i}, p_{l_i+1}, \ldots, p_{r_i}])$ 的值。

为此，您最多可以进行 30 次如下形式的询问：

• 选择任意两个整数 $1 \leq l \leq r \leq n$，然后您将收到 $\text{MEX}([p_l, p_{l+1}, \ldots, p_r])$ 的值。

$*$ 一个 $0$ 到 $n-1$ 的整数排列是一个包含 $n$ 个元素的序列，其中从 $0$ 到 $n-1$ 的每个整数都恰好出现一次。例如，序列 $[0,3,1,2]$ 是一个排列，但序列 $[0,0,2,1]$ 不是。

$†$ 一个序列的 $\text{MEX}$ 定义为该序列中没有出现的最小非负整数。例如，$\text{MEX}([0,0,1,3]) = 2$，$\text{MEX}([1,2,2]) = 0$。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \leq t \leq 100$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $n$ 和 $q$ ($4 \leq n \leq 10^4$, $1 \leq q \leq 3 \cdot 10^5$) —— 分别是排列的大小和区间的数量。

接下来的 $q$ 行中，第 $i$ 行包含两个整数 $l_i$, $r_i$ ($1 \leq l_i \leq r_i \leq n$)。

保证所有测试用例的 $n$ 的总和不超过 $10^4$，$q$ 的总和不超过 $3 \cdot 10^5$。

额外约束：保证在同一测试用例中没有重复的区间。

交互过程

要提出询问，请按以下格式输出一行（不带引号）： ? l r ($1 \leq l \leq r \leq n$)

评测机将返回一个整数，即 $\text{MEX}([p_l, p_{l+1}, \ldots, p_r])$ 的值。

当您找到答案时，请按以下格式输出一行： ! x ($0 \leq x \leq n$)

在此之后，继续处理下一个测试用例，或者如果是最后一个测试用例则终止程序。打印答案不计入询问次数。

交互器不是自适应的，这意味着排列的值在参与者提出询问之前就已经确定。

如果您的程序进行了超过 30 次询问，它应立即终止，并收到 Wrong Answer 的判定。否则，您可能会得到任意判定，因为您的解决方案将继续从已关闭的流中读取。

在打印询问后，请不要忘记输出行尾并刷新输出缓冲区。否则，您可能会得到 Idleness Limit Exceeded 的判定。为此，请使用：

• C++: fflush(stdout) 或 cout.flush()
• Java: System.out.flush()
• Pascal: flush(output)
• Python: stdout.flush()
• 其他语言请参阅文档。

黑客格式

对于黑客攻击，请使用以下格式。

输入的第一行应包含一个整数 $t$ ($1 \leq t \leq 100$) —— 测试用例的数量。

每个测试用例的第一行应包含两个整数 $n$ 和 $q$ ($4 \leq n \leq 10^4$, $1 \leq q \leq 3 \cdot 10^5$) —— 分别是排列的大小和给出的区间数量。

第二行应包含 $n$ 个整数 $p_1, p_2, \ldots, p_n$ —— 其中 $p_i$ 是排列的第 $i$ 个元素。应保证 $p$ 是一个包含 $0$ 到 $n-1$ 整数的排列。

接下来的 $q$ 行中，第 $i$ 行应包含两个整数 $l_i$, $r_i$ ($1 \leq l_i \leq r_i \leq n$)。

应保证所有测试用例的 $n$ 的总和不超过 $10^4$，$q$ 的总和不超过 $3 \cdot 10^5$。

额外约束：在同一测试用例中不应有重复的区间。

样例输入

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 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]$。第三个区间是最优的，因为 $\text{MEX}([p_1,p_2,p_3]) = \text{MEX}([0,3,1]) = 2$，这是最大值。

在我们的第一次询问中，我们询问了 $l=1, r=3$，裁判给出了值 $\text{MEX}([p_1,p_2,p_3]) = 2$。在第二次询问中，我们询问了 $l=4, r=4$，裁判给出了值 $\text{MEX}([p_4]) = 0$。同样地，$\text{MEX}([p_1]) = 1$，$\text{MEX}([p_1,p_2,p_3,p_4]) = 4$。

我们最终找出了我们寻找的答案是 $2$。

在第二个样例中，$p = [3,5,0,1,4,2]$。

在第三个样例中，$p = [0,1,2,3]$。

请注意，这仅仅是交互方式的一个解释，并未展示解决此问题的任何策略。

你好！你提的这几个问题都非常关键，尤其是你给的这份代码，它背后涉及的逻辑确实有点绕。我们一步一步来拆解。

坦率地说，你看不懂是正常的，因为这份代码的解法（通过二分查找一个“交叉点”）是用于解决这道题的 困难版本 (D2) 的。D1 版本给的查询限制 $\max(300, \lceil \frac{n}{2} \rceil + 2)$ 非常宽松，尤其是当 $n$ 很大时（比如 $n=10000$），限制高达 5002 次，暗示可能存在 $O(n)$ 的解法。

而你贴的这份代码，查询次数是 $O(\log q)$ 级别的（$q$ 是区间数量），大约只需要 40-50 次查询，这远远低于 D1 的限制（当然也符合 D1 的限制）。

我们就按这份 $O(\log q)$ 的代码逻辑来分析，因为它更精妙，也能回答你的所有问题。

---

1. 为什么可以二分？

二分查找的前提是单调性。在这份代码里，二分的对象不是最终答案 (MEX 值)，而是那个被“过滤”后的区间列表 qry 的下标。

二分查找的可行性建立在两个关键点上：

关键点一：区间过滤 (Pruning)

首先，代码对所有区间进行了排序和过滤。

C++

sort(a.begin(),a.end()); // 1. 按 l 升序, l 相同按 r 升序
vector<PII> qry;
for(int i=0;i<m;i++){
    // 2. 核心过滤
    if(!qry.empty()&&qry.back().second>=a[i].second){
        continue;
    }
    qry.push_back({a[i].first,a[i].second});
}

这个过滤是在做什么？它在移除“被完全包含”的区间。

我们要利用一个核心性质：

MEX 性质： 如果区间 $A$ 是区间 $B$ 的一个子区间（$S_A \subseteq S_B$），那么 $\text{MEX}(A) \le \text{MEX}(B)$。

证明： $B$ 缺少的最小非负整数是 $\text{MEX}(B)$。$A$ 缺少的数字集合 $M_A$ 必然包含 $B$ 缺少的数字集合 $M_B$（$M_B \subseteq M_A$）。因此，$A$ 缺少的最小非负整数 $\text{MEX}(A)$ 必然小于等于 $\text{MEX}(B)$。

我们要找的是 $\max(\text{MEX})$，所以如果区间 a[i] 被 qry.back() 包含，a[i] 的 MEX 不可能超过 qry.back() 的 MEX，我们就可以安全地跳过 a[i]。

• 排序后： $l$ 是非递减的。

• if 条件： if (qry.back().second >= a[i].second)

  • 因为排过序，a[i].first >= qry.back().first（大部分情况）。

  • 这个条件检查的是：新区间 a[i] 的右端点 $r_i$ 是否小于等于已保留区间 qry.back() 的右端点 $r_b$。

  • 如果 $l_i \ge l_b$ 且 $r_i \le r_b$，说明 a[i] 是 qry.back() 的子区间，$\text{MEX}(a[i]) \le \text{MEX}(qry.back())$，所以 a[i] 不可能是最优解（除非它等于最优解），可以跳过。

经过这个过滤，我们得到了一个列表 qry，其中 $r_i$ 是严格递增的。这个列表保留了所有“有希望成为最大MEX”的候选区间。

---

2. 这个二分板子是什么意思？

你给的代码中的板子是：

C++

int lo=0, hi=qry.size();
while(lo < hi){
    int mid = lo + hi >> 1;
    auto [l,r] = qry[mid];
    if(query(l,n) < query(1,r)) // check(mid)
        hi = mid; // 答案在 [lo, mid] 区间内
    else
        lo = mid + 1; // 答案在 [mid+1, hi] 区间内
}
// 循环结束时 lo == hi

这个板子和我上面分析的 [true, ..., false ...] 不太一样，我们来换个角度。

代码里的 check(mid) 是 query(l,n) < query(1,r)。

它在找这样一个 lo：

• check(lo) 是 false。

• check(lo-1) 是 true。

它在找 第一个 false 的位置。

• if (check(mid)) 为 true：mid 位置是 true。我们想要的“第一个 false” 肯定在 mid 的右边。

  • 代码：if(query(l,n) < query(1,r)) 为 true，执行 hi = mid。

  • 等等，这和我的分析反了。

• 让我们重新看代码：

  • if (query(l,n) < query(1,r))：这是 check(mid) == true。

  • hi = mid;：如果 mid 是 true，说明“分界点”在 mid 或者 mid 的左边。我们把搜索范围缩小到 [lo, mid)。

  • else (check(mid) == false)：

  • lo = mid + 1;：如果 mid 是 false，说明“分界点”一定在 mid 的右边。我们把搜索范围缩小到 [mid + 1, hi)。

• 搜索范围： [lo, hi) (左闭右开)。

• 循环结束： lo == hi。

• lo 的含义： 它是满足 check(lo) == false 的第一个元素的下标。

这正是 std::lower_bound 的逻辑。它在查找 [true, true, true, false, false, false] 中第一个 false 的位置。

这和你常用的板子是等价的，只是搜索的区间和更新逻辑不同。

你的板子：

C++

int l = 0, r = n - 1; // [l, r] 闭区间
while (l < r) {
    int mid = l + r >> 1;
    if (q[mid] >= x) // check(mid) = true
        r = mid; // 答案在 [l, mid]
    else
        l = mid + 1; // 答案在 [mid+1, r]
}
// 结束时 l == r, 含义是第一个满足 check(l) == true 的位置

你的板子在找第一个 true。这个题解的板子在找第一个 false。它们都是在找单调序列上的分界点，本质是一样的。

---

3. 如何用二分板子才不会 TLE？

二分查找 TLE 的唯一原因就是死循环。死循环的根源在于 while(l < r) 循环中，l 和 r 没有缩小范围。

这通常发生在区间只剩 2 个元素时，例如 l = 0, r = 1。

核心规则：mid 的取值必须和 l、r 的更新配对

情况一：更新 r 时保留 mid（例如 r = mid）

这是你常用的板子，用于查找下界 (lower_bound)。

C++

while (l < r) {
    int mid = l + r >> 1; // 1. 向下取整
    if (check(mid)) {
        r = mid; // 2. r 的更新
    } else {
        l = mid + 1;
    }
}

• 为什么不会死循环？

• 假设 l = 0, r = 1。

• mid = (0 + 1) / 2 = 0。

• 如果 check(0) 为 true，r = mid = 0。此时 l = 0, r = 0，循环结束。

• 如果 check(0) 为 false，l = mid + 1 = 1。此时 l = 1, r = 1，循环结束。

• 这个板子是绝对安全的。

情况二：更新 l 时保留 mid（例如 l = mid）

这个板子用于查找上界 (upper_bound)，或者“最后一个 true”。

C++

while (l < r) {
    // 错误示范
    int mid = l + r >> 1; // 1. 向下取整
    if (check(mid)) {
        l = mid; // 2. l 的更新
    } else {
        r = mid - 1;
    }
}

• 为什么会死循环？

• 假设 l = 0, r = 1。

• mid = (0 + 1) / 2 = 0。

• 如果 check(0) 为 true，l = mid = 0。l 和 r 保持 0, 1 不变。死循环！

• 如果 check(0) 为 false，r = mid - 1 = -1。循环结束。

正确的修改：

C++

while (l < r) {
    int mid = l + r + 1 >> 1; // 1. 向上取整
    if (check(mid)) {
        l = mid; // 2. l 的更新
    } else {
        r = mid - 1;
    }
}

• 为什么不会死循环？

• 假设 l = 0, r = 1。

• mid = (0 + 1 + 1) / 2 = 1。

• 如果 check(1) 为 true，l = mid = 1。此时 l = 1, r = 1，循环结束。

• 如果 check(1) 为 false，r = mid - 1 = 0。此时 l = 0, r = 0，循环结束。

• 这个板子是绝对安全的。

总结：防止 TLE 的黄金法则

1. r = mid 配对 mid = l + r >> 1 (向下取整)

2. l = mid 配对 mid = l + r + 1 >> 1 (向上取整)

只要遵守这个配对，你的 [l, r] 闭区间板子就永远不会死循环。你常用的 r = mid 和 l = mid + 1 配 l + r >> 1 是第一种情况，是完全正确的。

题解基本思路

好的，我们来重新梳理并总结一下这个解法的正确逻辑。

你之前的直觉完全正确，我第一次的分析是反的。集合越大，MEX 只会不变或增大。

以下是基于这个正确性质的完整分析：

1. 核心性质：MEX 的单调性

• MEX 定义： 集合中未出现的最小非负整数。

• 关键性质： 如果集合 $A$ 是集合 $B$ 的子集（$A \subseteq B$），那么 $\text{MEX}(A) \le \text{MEX}(B)$。

• 为什么？

  • 假设 $\text{MEX}(A) = m$。这意味着 $A$ 中包含 $\{0, 1, \dots, m-1\}$，但不包含 $m$。

  • 因为 $A \subseteq B$，所以 $B$ 也必然包含 $\{0, 1, \dots, m-1\}$。

  • 此时 $B$ 缺少的最小非负整数（即 $\text{MEX}(B)$）至少是 $m$。

  • （如果 $B$ 恰好也不包含 $m$，则 $\text{MEX}(B) = m$；如果 $B$ 中包含了 $m$，则 $\text{MEX}(B)$ 会大于 $m$）。

• 推论：

  • 往集合里添加元素，MEX 只会不变或增大。

  • 从集合里删除元素，MEX 只会不变或减小。

---

2. 区间过滤 (Pruning)

代码首先对区间进行了排序和过滤：

C++

sort(a.begin(),a.end()); // 按 l 排序
vector<PII> qry;
for(int i=0;i<m;i++){
    if(!qry.empty()&&qry.back().second>=a[i].second){
        continue;
    }
    qry.push_back({a[i].first,a[i].second});
}

• 排序 保证了 $l$ 是非递减的。

• if 语句 过滤掉了那些被前一个区间“包含”的区间。因为我们的目标是 $\max(\text{MEX})$，根据性质 1，被包含的子区间 $[l_i, r_i]$ 的 MEX 不可能超过包含它的区间 $[l_b, r_b]$ 的 MEX，所以可以安全地丢弃。

• 结果： 我们得到一个列表 qry，其中 $r_i$ (右端点) 是严格递增的，而 $l_i$ (左端点) 是非递减的。

---

3. 二分查找的单调性

我们在 qry 列表的下标上进行二分。二分的 check 条件是 check(mid) = (f(mid) < g(mid))，其中：

1. g(mid) = query(1, R) （其中 $R = qry[mid].second$）

   • 当 mid 增大时，$R$ 严格增大。

   • 区间 [1, R] 变大，它包含的元素集合 $S$ 只会变大 ($S \subseteq S'$)。

   • 根据核心性质，MEX 值只会不变或增大 (非递减 ↗)。

2. f(mid) = query(L, n) （其中 $L = qry[mid].first$）

   • 当 mid 增大时，$L$ 非递减。

   • 区间 [L, n] 变小（或不变），它包含的元素集合 $S$ 只会变小 ($S' \subseteq S$)。

   • 根据核心性质，MEX 值只会不变或减小 (非递增 ↘)。

我们正在 mid 上搜索 f(mid) < g(mid) 这个条件：

• f(mid) 是一个 (↘) 非递增函数。

• g(mid) 是一个 (↗) 非递减函数。

随着 mid 增大，f(mid) 的值在减小（或不变），g(mid) 的值在增大（或不变）。

f(mid) < g(mid) 这个布尔表达式，会从一连串的 false 变为一连串的 true。

[false, false, ..., false, true, true, ..., true]

（也可能全是 false 或全是 true，但绝不会在 true 之后再出现 false）。

这是一个完美的单调序列，因此我们可以对其进行二分查找。

---

4. 二分板子与最终答案

你给出的代码中使用的板子是：

C++

int lo=0, hi=qry.size();
while(lo < hi){
    int mid = lo + hi >> 1;
    if(query(l,n) < query(1,r)) // check(mid) == true
        hi = mid;
    else // check(mid) == false
        lo = mid + 1;
}

• 这是一个在 [lo, hi) 左闭右开区间上查找的板子。

• if (check(mid)) 为 true，说明 mid 可能是第一个 true，也可能在它左边，所以搜索 [lo, mid)，即 hi = mid。

• if (check(mid)) 为 false，说明第一个 true 一定在 mid 的右边，所以搜索 [mid + 1, hi)，即 lo = mid + 1。

• 循环结束时： lo == hi，lo 指向的就是 [false, ..., true, ...] 序列中第一个 true 的位置。

这个 lo 就是 f(mid) 和 g(mid) 两条曲线的“交叉点”。这道题（特别是 D2）的结论就是，全局的最大 MEX 一定出现在这个交叉点 lo 或者它前一个 lo-1 所对应的区间上。

因此，代码最后只需要花两次查询 query(qry[lo].first, qry[lo].second) 和 query(qry[lo-1].first, qry[lo-1].second)（注意边界检查），取它们的最大值，就是最终答案。