CF2163D 交互库实现

// #define HD
#include <bits/stdc++.h>

#include "testlib.h"
using namespace std;

struct MexHelper {
  int n;
  vector<int> pos;      // pos[v] = index of value v in permutation (1-indexed)
  vector<int> prefMin;  // prefMin[m] = min pos[0..m-1]
  vector<int> prefMax;  // prefMax[m] = max pos[0..m-1]

  MexHelper() = default;
  MexHelper(int n_, const vector<int> &p1) { init(n_, p1); }

  void init(int n_, const vector<int> &p1) {
    n = n_;
    pos.assign(n, 0);
    for (int i = 1; i <= n; ++i) pos[p1[i]] = i;

    prefMin.assign(n + 1, n + 1);
    prefMax.assign(n + 1, 0);
    // m = 0: 空集，min=+inf, max=0，必满足任意 [l,r]
    for (int m = 1; m <= n; ++m) {
      int pv = pos[m - 1];
      prefMin[m] = min(prefMin[m - 1], pv);
      prefMax[m] = max(prefMax[m - 1], pv);
    }
  }

  // O(log n) mex on [l..r]
  int mexOnSubarray(int l, int r) const {
    int lo = 0, hi = n;  // 最大 m 使得所有 {0..m-1} 的 pos 都在 [l,r]
    while (lo < hi) {
      int mid = (lo + hi + 1) >> 1;
      if (prefMin[mid] >= l && prefMax[mid] <= r)
        lo = mid;
      else
        hi = mid - 1;
    }
    return lo;  // mex = lo
  }
};

// 计算“所有给定区间中 mex 的最大值”，O(n+q)
static int computeAnswer(int n, const vector<int> &p1,
                         const vector<pair<int, int>> &ranges) {
  // pos[v]
  vector<int> pos(n);
  for (int i = 1; i <= n; ++i) pos[p1[i]] = i;

  // mxR[L] = max_{l' <= L} r'
  vector<int> bestRByL(n + 1, -1);
  for (auto [l, r] : ranges) {
    bestRByL[l] = max(bestRByL[l], r);
  }
  vector<int> mxR(n + 1, -1);
  for (int L = 1; L <= n; ++L) mxR[L] = max(mxR[L - 1], bestRByL[L]);

  // 扩张包络 [L..R] 覆盖 {0..m-1}
  int L = n + 1, R = 0, ans = 0;
  for (int m = 1; m <= n; ++m) {
    int posNew = pos[m - 1];
    L = min(L, posNew);
    R = max(R, posNew);
    if (mxR[L] >= R)
      ans = m;
    else
      break;
  }
  return ans;  // 若存在覆盖全体的区间，答案可达 n
}

int main(int argc, char *argv[]) {
  registerInteraction(argc, argv);

  int T = inf.readInt(1, 100, "t");
  cout << T << endl;  // flush

  long long totalQueries = 0;

  for (int tc = 1; tc <= T; ++tc) {
    int n = inf.readInt(4, 10000, "n");
    int q = inf.readInt(1, 300000, "q");
    int MAX_Q = std::max(300, (int)ceil(n / 2.0) + 2);
#ifdef HD
    MAX_Q = 30;
#endif
    // 读 permutation（1-indexed）
    vector<int> p1(n + 1);
    vector<int> seen(n, 0);
    for (int i = 1; i <= n; ++i) {
      int v = inf.readInt(0, n - 1, "p_i");
      if (seen[v]) quitf(_fail, "Input permutation contains duplicates.");
      seen[v] = 1;
      p1[i] = v;
    }
    for (int v = 0; v < n; ++v) {
      if (!seen[v]) quitf(_fail, "Input permutation is missing value %d.", v);
    }

    vector<pair<int, int>> ranges(q);
    for (int i = 0; i < q; ++i) {
      int l = inf.readInt(1, n, "l_i");
      int r = inf.readInt(l, n, "r_i");
      ranges[i] = {l, r};
    }

    // 输出给选手：n q 和所有区间
    cout << n << ' ' << q << endl;
    for (auto [l, r] : ranges) cout << l << ' ' << r << endl;

    // 预处理：O(n) 构建 mex 查询助手（O(log n) 查询）
    MexHelper mexer(n, p1);

    // 正确答案：O(n+q)
    int correct = computeAnswer(n, p1, ranges);

    int queriesUsed = 0;
    while (true) {
      // 注意：不要把提示语当作正则；这里读一个“词”
      string op = ouf.readWord();

      if (op == "?") {
        int l = ouf.readInt(1, n, "l");
        int r = ouf.readInt(l, n, "r");

        ++queriesUsed;
        ++totalQueries;
        if (queriesUsed > MAX_Q) {
          quitf(_wa, "Too many queries in test #%d: %d used (limit %d).", tc,
                queriesUsed, MAX_Q);
        }

        int mex = mexer.mexOnSubarray(l, r);  // O(log n)
        cout << mex << endl;                  // flush
      } else if (op == "!") {
        int x = ouf.readInt(0, n, "answer");
        if (x != correct) {
          quitf(_wa, "Wrong answer on test #%d: got %d, expected %d.", tc, x,
                correct);
        }
        break;  // 进入下一组
      } else {
        quitf(_wa, "Unknown token '%s'. Expected '?' or '!'.", op.c_str());
      }
    }
  }

  quitf(_ok, "Accepted. Total queries used: %lld.", totalQueries);
  return 0;
}

3
4 3
0 3 1 2
1 2
2 4
1 3
6 6
3 5 0 1 4 2
1 2
2 4
3 3
4 6
5 5
6 6
4 4
0 1 2 3
1 1
2 2
3 3
4 4