交互题

[[区间合并]]

D1. Diadrash (Easy Version)

时间限制：每个测试 3 秒
内存限制：每个测试 256 MB

问题描述

这是问题的简单版本。两个版本的区别在于，在此版本中，您最多可以进行 $\max(300, \lceil \frac{n}{2} \rceil + 2)$ 次查询。只有解决了此问题的所有版本，您才能进行破解。

这个问题是交互式的。

有一个整数从 $0$ 到 $n-1$ 的排列 $p$ 对您隐藏。
此外，还会提供 $q$ 个区间 $[l_1, r_1], [l_2, r_2], \dots, [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}, \dots, p_{r_i}])$ 的值。
为此，您最多可以进行以下形式的 $\max(300, \lceil \frac{n}{2} \rceil + 2)$ 次查询：

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

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

$†$ 序列的 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}, \dots, p_r])$ 的值。

当您找到答案时，请按以下格式输出一行：

! x

($0 \leq x \leq n$)

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

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

如果您的程序进行的查询次数超过 $\max(300, \lceil \frac{n}{2} \rceil + 2)$，它应立即终止，并收到错误答案的判定。否则，您可能会得到任意判定，因为您的解决方案将继续从已关闭的流中读取。

在打印查询后，不要忘记输出行末并刷新输出。否则，您可能会收到超时判定。为此，请使用：

• 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, \dots, 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]$。

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

赛时WA 2代码

• 其实就是我随手写的，直接查询每一个给的那个区间的值，找最大值

  // Problem: CF 2163 D1
  // Contest: Codeforces - Codeforces Round 1063 (Div. 2)
  // URL: https://codeforces.com/contest/2163/problem/D1
  // Memory Limit: 256 MB
  // Time Limit: 3000 ms
  // 
  // Powered by CP Editor (https://cpeditor.org)
  
  #include <bits/stdc++.h>
  using namespace std;
  typedef long long LL;
  typedef pair<LL,LL> PII;
  const int N=1e9+7,INF=0x3f3f3f3f;
  
  int query(int l,int r){
      cout<<"?"<<" "<<l<<" "<<r<<endl;
      int x;
      cin>>x;
      return x;
  }
  
  void solve() {
      int n,m;
      cin>>n>>m;
      vector<PII> a(m);
      for(int i=0;i<m;i++){
          cin>>a[i].first>>a[i].second;
      }    
      int ans=0;
      for(int i=0;i<m;i++){
          int t=query(a[i].first,a[i].second);
          ans=max(ans,t);
      }
      cout<<"!"<<" "<<ans<<endl;
      return;
  }
  
  int main() {
      int t;
      cin >> t;
      while (t--) {
          solve();
      }
      return 0;
  }
  

WA 6(估计查询超时)

// Problem: CF 2163 D1
// Contest: Codeforces - Codeforces Round 1063 (Div. 2)
// URL: https://codeforces.com/contest/2163/problem/D1
// Memory Limit: 256 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const int N=1e9+7,INF=0x3f3f3f3f;

int query(int l,int r){
    cout<<"?"<<" "<<l<<" "<<r<<endl;
    int x;
    cin>>x;
    return x;
}

void solve() {
    int n,m;
    cin>>n>>m;
    vector<PII> a(m);
    for(int i=0;i<m;i++){
        cin>>a[i].first>>a[i].second;
    }    
    sort(a.begin(),a.end());

    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});
    }


    int ans=0;
    for(int i=0;i<qry.size();i++){
        int t=query(qry[i].first,qry[i].second);
        ans=max(ans,t);
    }
    cout<<"!"<<" "<<ans<<endl;
    return;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

看哥哥AC代码

// Problem: CF 2163 D1
// Contest: Codeforces - Codeforces Round 1063 (Div. 2)
// URL: https://codeforces.com/contest/2163/problem/D1
// Memory Limit: 256 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const int N=1e9+7,INF=0x3f3f3f3f;

int query(int l,int r){
    cout<<"?"<<" "<<l<<" "<<r<<endl;
    int x;
    cin>>x;
    return x;
}

void solve() {
    int n,m;
    cin>>n>>m;
    vector<PII> a(m);
    for(int i=0;i<m;i++){
        cin>>a[i].first>>a[i].second;
    }    
    sort(a.begin(),a.end());

    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});
    }

    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)) hi=mid;
        else lo=mid+1;
    }

    int ans=0;
    if(lo<qry.size()) ans=max(ans,query(qry[lo].first,qry[lo].second));
    if(lo) ans=max(ans,query(qry[lo-1].first,qry[lo-1].second));
    cout<<"!"<<" "<<ans<<endl;
    return;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

jiangly 代码

#include <bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;

using u128 = unsigned __int128;
using i128 = __int128;

int query(int l, int r) {
    std::cout << "? " << l << " " << r << std::endl;
    int ans;
    std::cin >> ans;
    return ans;
}

void solve() {
    int n, q;
    std::cin >> n >> q;

    std::vector<std::array<int, 2>> qry(q);
    for (int i = 0; i < q; i++) {
        int l, r;
        std::cin >> l >> r;
        qry[i] = {l, r};
    }

    {
        std::sort(qry.begin(), qry.end());
        std::vector<std::array<int, 2>> nqry;
        for (auto [l, r] : qry) {
            if (!nqry.empty() && r <= nqry.back()[1]) {
                continue;
            }
            nqry.push_back({l, r});
        }
        qry = std::move(nqry);
    }

    q = qry.size();

    int lo = 0, hi = q;
    while (lo < hi) {
        int x = (lo + hi) / 2;
        auto [l, r] = qry[x];
        if (query(l, n) < query(1, r)) {
            hi = x;
        } else {
            lo = x + 1;
        }
    }

    int ans = 0;
    int x = lo;
    if (x < q) {
        auto [l, r] = qry[x];
        ans = std::max(ans, query(l, r));
    }
    if (x > 0) {
        auto [l, r] = qry[x - 1];
        ans = std::max(ans, query(l, r));
    }

    std::cout << "! " << ans << std::endl;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t;
    std::cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}

AI 对于题目思路的分析

我们来一步步分析这道题。这道题（D1）是 D2 的一个提示，它给的查询限制 $\max(300, \lceil \frac{n}{2} \rceil + 2)$ 非常“宽松”，这暗示我们 $O(n)$ 甚至 $O(q)$（如果 $q$ 不大）的查询都是可接受的。

但我们先看你的代码。

步骤 1：分析你的 WA2 代码

C++

    int ans=0;
    for(int i=0;i<m;i++){ // m 就是 q
        int t=query(a[i].first,a[i].second);
        ans=max(ans,t);
    }

你的思路非常直接：“把 $q$ 个区间一个一个全问一遍，然后取最大值。”

这个思路在逻辑上是完全正确的。但它为什么会 WA2 呢？

我们来看限制：

• $q$ (你代码里的 m) $\le 3 \cdot 10^5$

• $n \le 10^4$

• 查询次数限制: $\max(300, \lceil \frac{n}{2} \rceil + 2)$。

  • 假设 $n=10000$，查询限制 $\approx \lceil 10000 / 2 \rceil + 2 = 5002$ 次。

问题来了：

如果一个测试用例 $q = 300,000$ 怎么办？

你的代码会尝试进行 300,000 次查询。

但查询限制只有 5002 次。

在交互题中，当你超过了查询次数限制，评测机通常会立刻停止你的程序并返回 "Wrong Answer"。

结论： 你的 WA2 不是逻辑错了，而是“查询超时”（Query Limit Exceeded）了。我们必须找到一个方法，在远少于 $q$ 次查询（最好是 $O(\log q)$ 或 $O(n)$ 级别）内找到答案。

---

步骤 2：jiangly 的第一个优化（剪枝）

既然不能全问，我们能不能“少问一点”？

jiangly 的代码在查询前，先对 $q$ 个区间做了一次“大扫除”：

C++

    {
        std::sort(qry.begin(), qry.end()); // 按 l 排序
        std::vector<std::array<int, 2>> nqry;
        for (auto [l, r] : qry) {
            if (!nqry.empty() && r <= nqry.back()[1]) {
                // 如果这个区间的 r 比 "已保留" 的
                // 最后一个区间的 r 还小，就跳过
                continue;
            }
            nqry.push_back({l, r});
        }
        qry = std::move(nqry); // 用"净化"过的列表替换
    }

这段代码在做什么？

1. 它首先按 $l$ 给所有区间 $[l, r]$ 排序。

2. 然后它遍历这个列表，只保留“有意义”的区间。

3. “无意义”的区间： 假设我们保留的最后一个区间是 A = [2, 7]。现在我们看到了一个新区间 B = [3, 5]。

   • 因为 $l$ 排序了，所以 B.l (3) $\ge$ A.l (2)。

   • jiangly 检查：B.r (5) $\le$ A.r (7)？是的。

   • 这说明 B 完全被 A 包含 (A 不一定完全包含 B，但在这个例子里 [2,7] 确实包含了 [3,5]。更准确地说，是 $l_A \le l_B$ 且 $r_B \le r_A$ 的情况，但这里 $l_A$ 不一定是 nqry.back()[0]，而是某个更早的 $l$，但 $r_A$ 是 nqry.back()[1]）。

   • （更正我的分析，看 jiangly 的代码）

   • 他是按 $l$ 排序。假设列表是 [2, 7]，[3, 5]，[4, 9]。

   • 1. nqry 为空，加入 [2, 7]。 nqry = {[2, 7]}
   • 1. 看到 [3, 5]。nqry.back()[1] 是 7。 5 <= 7 成立。跳过 [3, 5]。
   • 1. 看到 [4, 9]。nqry.back()[1] 是 7。 9 <= 7 不成立。加入 [4, 9]。 nqry = {[2, 7], [4, 9]}

   • 他在删除所有满足 $l_A \le l_B$ 且 $r_B \le r_A$ 的区间 B。

为什么可以跳过 B = [3, 5]？

• 我们要找的是最大 MEX。

• [3, 5] 对应的序列是 [p_3, p_4, p_5]。

• [2, 7] 对应的序列是 [p_2, p_3, p_4, p_5, p_6, p_7]。

• [p_3, \dots, p_5] 是 [p_2, \dots, p_7] 的一个子集。

• MEX 的关键性质： 当你往一个集合里添加更多数字时，它的 MEX 只可能不变或增加，绝不可能减少。

• $\text{MEX}([p_2, \dots, p_7]) \ge \text{MEX}([p_3, \dots, p_5])$

• 既然 [2, 7] 的 MEX 已经保证不小于 [3, 5] 的 MEX，而我们又要找最大值，那我们根本不需要去问 [3, 5] 了！问 [2, 7] 就够了。

结论： 这个“剪枝”步骤，正确地删除了所有“被其他区间包含”的“小区间”，因为它们的 MEX 不可能是最大值。

---

步骤 3：jiangly 的第二个优化（二分）

“剪枝”后，qry 列表变小了，但它最坏情况还是可能有 $n$ 个区间（比如 [1,1], [2,2], \dots, [n,n]）。

$O(n)$ 次查询（约 5002 次）在 D1 版本里是可以接受的！

但 jiangly 连 $O(n)$ 都不想用，他用了一个 $O(\log n)$ 的“黑魔法”：在“净化”后的 $q$ 个区间索引上进行二分。

C++

    int lo = 0, hi = q; // q 是净化后的区间数量
    while (lo < hi) {
        int x = (lo + hi) / 2;
        auto [l, r] = qry[x]; // 取出第 x 个区间 [l, r]
        if (query(l, n) < query(1, r)) {
            hi = x;
        } else {
            lo = x + 1;
        }
    }

这绝对是这道题最难理解的部分。

1. 他在二分什么？ 他在二分一个索引 x，他猜测答案（最大 MEX）就藏在 qry[x] 这个区间附近。

2. 比较函数是什么？ query(l, n) < query(1, r)

   • m1 = MEX([p_l, \dots, p_n])

   • m2 = MEX([p_1, \dots, p_r])

   • 目标区间 [l, r] 恰好是 [l, n] 和 [1, r] 的交集。

   • 这个比较函数是在“猜”：

     • 如果 $m_1 < m_2$，说明在 $[l, n]$ 这个后缀里，“缺失的最小数” ($m_1$) 比 $[1, r]$ 这个前缀里“缺失的最小数” ($m_2$) 要小。这暗示“宝藏”（$0, 1, 2, \dots$ 这些小数）更可能不在 $[l, n]$ 里，而在它左边。所以他猜答案在 x 的左侧（hi = x）。

     • 如果 $m_1 \ge m_2$，则反之，猜答案在 x 或其右侧（lo = x + 1）。

这是一个非常巧妙（且不一定 100% 严谨，但能用）的二分检查，它利用 $\text{MEX}$ 的性质来“导航”，判断最大值可能在区间的左半边还是右半边。

这个二分会把查询次数从 $O(q)$ 降到 $O(\log q)$（每次循环查 2 次，所以是 $O(\log q)$ 次查询）。

步骤 4：收尾

C++

    int ans = 0;
    int x = lo;
    if (x < q) {
        auto [l, r] = qry[x];
        ans = std::max(ans, query(l, r));
    }
    if (x > 0) {
        auto [l, r] = qry[x - 1];
        ans = std::max(ans, query(l, r));
    }
    
    std::cout << "! " << ans << std::endl;

二分查找（lo = x + 1 这种写法）结束后，lo (即 x) 指向的是“第一个不满足条件的”或“最后一个满足条件的”的邻居。

所以，为了保险起见，jiangly 把二分停下的位置 x 和它前面一个位置 x-1 都查了一遍。因为真正的最大值很可能在这两个索引之一。

---

总结与提升 (D1 版本)

1. 你的 WA2： 不是逻辑错误，而是查询次数超限。

2. 核心思想 1 (剪枝)： 必须减少查询。利用 $\text{MEX}$ 的性质（$\text{MEX}(\text{superset}) \ge \text{MEX}(\text{subset})$），我们可以安全地删除所有“被（其他给定的）区间所包含”的小区间。

3. 核心思想 2 (二分)： 即使剪枝后，区间数可能还是太多（比如 $O(n)$）。jiangly 用了一个非常高级的二分查找，在“区间列表的索引”上二分，用一个巧妙的 $\text{MEX}$ 比较来导航，把查询复杂度降到了 $O(\log q)$。

对于 D1 版本：

你其实不需要 jiangly 那么复杂的二分！

你只需要步骤 1 + 步骤 2（剪枝），然后再加一个简化版的查询：

D1 的 $O(n)$ 解法：

1. 找到 $0$ 在哪里。怎么找？

2. 用 $\lceil \frac{n}{2} \rceil + 2$ 次查询，我们可以二分查找 $0$ 的位置 pos_0。

   • query(1, mid)：如果 $\text{MEX} > 0$，说明 0 在 [1, mid] 里。hi = mid。

   • 如果 $\text{MEX} == 0$，说明 0 不在 [1, mid] 里。lo = mid + 1。

   • 这会消耗 $O(\log n)$ 次查询。

3. 用 $O(\log n)$ 次查询找到 $1$ 的位置 pos_1。（通过查询 $0$ 在不在区间来判断）

4. ... 我们可以用 $O(n \log n)$ 次查询找到所有 $n$ 个数的位置。这还是太多了。

D1 的正确 $O(n)$ 解法：

1. 找到 $0$ 的位置 pos_0：

   • 遍历 $i$ 从 1 到 $n$。

   • 问 query(i, i)。

   • 如果 query(i, i) > 0（即 $\text{MEX} > 0$），说明 $p_i \neq 0$。

   • 如果 query(i, i) == 0，说明 $p_i = 0$。

   • 这样你最多用 $n$ 次查询就能找到 pos_0。

2. 找到 $1$ 的位置 pos_1：

   • 已经知道 $0$ 在 pos_0。

   • 遍历 $i$ 从 1 到 $n$。

   • 问 query(min(i, pos_0), max(i, pos_0))。

   • 如果 $\text{MEX} == 2$，说明 0 和 1 都在这个区间里，所以 $p_i = 1$。

   • 如果 $\text{MEX} \le 1$，说明 $p_i \neq 1$。

   • 这又用了 $O(n)$ 次。

这个 $O(n^2)$ 查询的思路还是太慢。

让我们回到 D1 的限制：$\max(300, \lceil \frac{n}{2} \rceil + 2)$

这个 $\lceil \frac{n}{2} \rceil + 2$ 是个烟雾弹，300 才是关键（因为 $n$ 很大）。

这道题 D1 和 D2 的区别很小，D1 只是给了个 300 的“保底”查询，D2 没有。

jiangly 的 $O(\log q)$ 解法（总查询数 $O(\log q)$，如果算上最后的2次，就是 $O(\log q)$）远优于 $O(n)$，它能同时通过 D1 和 D2。

你学到了吗？关键是：你的 $O(q)$ 查询的想法，被“剪枝”优化到了 $O(q)$（但列表更短），再被“二分”优化到了 $O(\log q)$。

CF 题解思路

首先，请注意，如果一个范围完全在另一个范围内，则它是无用的。具体来说，假设我们有两个范围 $[l_1, r_1]$ 和 $[l_2, r_2]$ 。如果 $1 \le l_2 \le l_1 \le r_1 \le r_2 \le n$ ，那么我们知道 $\operatorname{MEX}(p[l_1 \ldots r_1]) \le \operatorname{MEX}(p[l_2 \ldots r_2])$ 。因此，我们必须只考虑范围 $[l_2, r_2]$ 。在清除这些范围之后，我们最多只剩下 $n$ 个范围。

这是显而易见的，因为对于每个可能的左端点，我们最多有一个可能的右端点（所有给定范围中最大的一个）。现在，假设我们也知道 $0$ 的位置。假设它是 $p_0$ 。

我们知道，如果某些范围不包括 $p_0$ ，它也是无用的。我声称，除去这些范围，我们必须考虑最多 $\lceil \frac{n}{2} \rceil$ 个可能的范围。具体来说，如果 $p_0 \le \frac{n}{2}$ ，我们只考虑左端点在 $p_0$ 之前的范围。否则，如果 $p_0 \ge \frac{n}{2}$ ，我们只考虑右端点在 $p_0$ 之后的范围。在这两种情况下，显然我们最多考虑 $\lceil \frac{n}{2} \rceil$ 范围。最后，请注意，我们并不关心 $p_0$ 的精确值，而只关心它是否在前半部分或后半部分。

因此，我们将执行形式为 $[1, \frac{n}{2}]$ 的查询，确定 $p_0$ 在哪一半中，清除无用的范围并查询其余范围。这将导致最多 $\lceil \frac{n}{2} \rceil + 1$ 个查询，从而解决问题。

CF 题解代码

#include <bits/stdc++.h>
using namespace std;

int LIM, Q;

int ask(int l, int r) {
    Q++;
    assert(Q <= LIM);
    cout << "? " << l << " " << r << endl;
    int ans; cin >> ans;
    return ans;
}

bool inside(int l, int r, bool toL, int n) {
    int midL = n / 2;
    if (toL) {
        return l <= midL;
    }
    else return r > midL;
}

void solve() {
    int n, q; cin >> n >> q;
    Q = 0;
    LIM = max(30, n / 2 + n % 2 + 5);
    vector<int> maxR(n+1, 0);
    for (int i = 1; i <= q; i++) {
        int l, r; cin >> l >> r;
        maxR[l] = max(maxR[l], r);
    }
    bool toL = (ask(1, n/2) > 0);
    int ans = 0, mx = 0;
    for (int i = 1; i <= n; i++) {
        if (maxR[i] > mx && inside(i, maxR[i], toL, n)) {
            ans = max(ans, ask(i, maxR[i]));
        }
        mx = max(mx, maxR[i]);
    }
    cout << "! " << ans << endl;
}

int main() {
    int t; cin >> t;
    while (t--) solve();
    return 0;
}