CF2163D2-Diadrash (Hard Version)
题意：
交互题。在有 \(n(n\leq 10^4)\) 个元素的排列中给定 \(q(q\leq 3×10^5)\) 个区间，求这些区间中MEX值的最大。可以询问区间 \([l,r]\) 的MEX，不超过30次。
大部分交互题的本质在二分，这题的难点就在于转化出可以二分的条件。
容易得到，一个大区间\([L,R]\) 如果完全包含了一个小区间 \([l,r]\)，那么 $MEX[L,R]\geq MEX[l,r] $。通过这个性质，小区间一定可以不用考虑。将小区间删去后，剩下最多 \(n\) 个区间。
接着考虑如何转化MEX：在一个排列中，\(MEX[l,r]\) 实际上就等于不在 \([l,r]\) 中的最小值，即：\(min(min[1,l-1],min[r+1,n])\)。而\(min[1,l-1]=MEX[l,n],min[r+1,n]=MEX[1,l]\)。所以可以得到：\(MEX[l,r]=min(MEX(l,n),MEX(1,r))\)。推出这个式子有什么用呢？
我们将区间按左端点排序，右端点一定也是递增的。从枚举的角度出发，随着 \(i\) 增大，\(l_i\) 和 \(r_i\) 都在增大，因此 \(MEX(l,n)\) 在递减，\(MEX(1,r)\) 在递增，而这两者 \(min\) 值的最大一定在中间某点取到。
考虑二分：由于我们要求的是 \(min(MEX(l,n),MEX(1,r))\)。如果区间 \(i\) 的 \(MEX(l_i,n)>MEX(1,r_i)\)，将 \(i\) 右移。此时 \(MEX(l_i,n)\) 减小，\(MEX(1,r_i)\) 增大；反之则将 \(i\) 左移。在二分过程中实时更新最大值，得到的最大值即是答案。
#include <iostream>
#include <vector>
using namespace std;typedef pair<int,int> PII;int query(int l, int r)
{cout << "? " << l << " " << r << endl;int t;cin >> t;return t;
}void solve()
{int n,q;cin >> n >> q;vector<int> maxr(n+10,-1);for (int i = 1 ; i <= q ; i++){int l,r;cin >> l >> r;maxr[l] = max(maxr[l],r);}int now = 0;vector<PII> p;for (int i = 1 ; i <= n ; i++){if (maxr[i] > now){now = maxr[i];p.push_back({i,now});}}int l = -1;int r = p.size();int ans = 0;while (l+1 != r){int mid = (l+r) >> 1;int L = p[mid].first;int R = p[mid].second;int a = query(1,R);int b = query(L,n);ans = max(ans,min(a,b));if (a > b) r = mid;else l = mid;}cout << "! " << ans << endl;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T;cin >> T;while (T--) solve();return 0;
}