Codeforces Round 1063 (Div. 2) 补题记录
D - Diadrash
题目大意：
本题为交互题，存在一个 \([0, \ n - 1]\) 的排列 \(p\)，以及 \(q\) 个区间。
每次询问 "\(? \ l \ r\)" 会返回区间 \([l, \ r]\) 的 \(Mex\)，最多可以询问 \(30\) 次。
问这 \(q\) 个区间的最大 \(Mex\) 为多少。
思路：
首先我们可以发现两个性质：
-
设 \(A = [l, \ r], B = [L, \ R]\)，若 \(A\) 被 \(B\) 所包含，则 \(Mex(A) \leq Mex(B)\)。
-
\(Mex(L, \ R) = min(min(p_1, \dots, p_{L-1}), min(p_{R+1}, \dots, p_n))\)
首先我们可以利用第一个性质减少区间的数量。而对于第二个性质，我们可以得到 \(Mex([L, \ R]) = min(Mex([L, \ n]), Mex([1, \ R]))\)。证明如下：
-
设 \(A(L) = Mex([L, \ n]), \ B(R) = Mex([1, \ R])\)
-
由性质二可得：\(A(L) = min(p_1, \dots, p_{L - 1}), \ B(R) = min(p_{R + 1}, \dots, p_n)\)
-
故 \(Mex([L, \ R]) = min(A(L), B(R))\)
然后我们设 \(f(i) = Mex([L_i, \ R_i]) = min(A(L_i), B(R_i))\)。那么有：
通过对区间排序，可以使得当 \(i\) 增大时，\(L_i\) 与 \(R_i\) 都是单调不减的。对于 \(A(L_i)\)，当 \(i\) 增大时，\(L_i\) 增大，\([L_i, \ n]\) 所覆盖区间缩小，因此\(A(L_i)\) 要么不变要么减小；而对于 \(B(R_i)\)，当 \(i\) 增大时，\(R_i\) 增大，\([1, \ R_i]\) 所覆盖区间扩大，因此\(B(R_i)\) 要么不变要么增大。
因此，我们对所有区间用二分模拟三分的方法，当 \(f(i) = A(L_i)\) 时，缩小 \(i\)，当 \(f(i) = B(R_i)\) 时，增大 \(i\)，同时更新答案即可。
code：
#include <bits/stdc++.h>
using namespace std;// #define endl '\n'
#define i64 long longvoid MuBai() {int n, q;cin >> n >> q;vector<pair<int, int>> range(q), merged;for (int i = 0; i < q; i ++ ) {cin >> range[i].first >> range[i].second;}ranges::sort(range, [&](auto A, auto B) {if (A.first == B.first) return A.second > B.second;return A.first < B.first;});int maxRight = -1;for (int i = 0; i < q; i ++ ) {if (range[i].second > maxRight) {merged.emplace_back(range[i]);maxRight = range[i].second;}}function<int(int, int)> ask = [&](int l, int r) {int res = 0;cout << "? " << l << ' ' << r << endl;cin >> res;return res;};int l = 1, r = merged.size(), ans = -1;while (l <= r) {int mid = (l + r) >> 1;int left = merged[mid - 1].first;int right = merged[mid - 1].second;int A = ask(left, n), B = ask(1, right);ans = max(ans, min(A, B));if (A > B) l = mid + 1;else r = mid - 1;}cout << "! " << ans << endl;
}int main() {// ios::sync_with_stdio(false);// cin.tie(nullptr), cout.tie(nullptr);int t; cin >> t;while (t -- ) MuBai();return 0;
}// 0 3 1 2
// 3 5 0 1 4 2
// 0 1 2 3