题解：CF2163D2 Diadrash (Hard Version)

elswzl · 2025-11-14 14:44:52 · 题解

首先，这类题有一个经典trick，就是对于一个 [0,n-1] 排列的某个子集的 \text{mex} 等价于其补集的 \min。证明显然。

对于此题，已知一个集合的 \text{mex} 的值，如果我们往这个集合加一个数字，这个值一定不会变小。由此可以推断原题中所有被其他询问包含的询问都是无用的。此时，区间仅剩 O(N) 个。假定剩余 m 个区间并且区间已经升序排序。

设 f_i = \min_{j=1}^{i}{p_j}，g_i = \min_{j=i}^{n}{p_j}，显然 f 与 g 分别是单调递减和单调递增的。同时可以得到 mex_{i=l}^{r}{p_i}=\min(f_{l-1},g_{r+1})。那么，对于所有询问得到的函数，一定是一个增函数和一个减函数对应位置的 \min。如图：

红点就是最终答案所在位置，二分选哪个区间即可。

有个细节是答案有可能取在极值点两边，所以最终答案要选择极值点附近两点比较大小。

次数 2\times \log_2{n}+2。

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10;
int a[N],n,q;
int ask(int l,int r){
    cout<<"? "<<l<<" "<<r<<endl;
    int ret;
    cin>>ret;return ret;
}
int l[N],r[N],m;
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);
    int T;cin>>T;
    while(T--){
        cin>>n>>q;
        for(int i=1;i<=n;i++)a[i]=i+1;
        while(q--){
            int l,r;cin>>l>>r;
            a[r]=min(a[r],l);
        }
        int mn=n+1;
        for(int i=n;i>=1;i--){
            if(a[i]>=mn)a[i]=i+1;
            else mn=min(a[i],mn);
        }
        m=0;
        for(int i=1;i<=n;i++)if(a[i]!=i+1)l[++m]=a[i],r[m]=i;//所有有用的区间
        int p=0;
        for(int i=1<<20;i;i>>=1){
            if(p+i<=m&&ask(l[p+i],n)>=ask(1,r[p+i]))p+=i;
        }
        int ans=0;
        if(p!=0)ans=max(ans,ask(l[p],r[p]));
        if(p+1<=m)ans=max(ans,ask(l[p+1],r[p+1]));
        cout<<"! "<<ans<<endl;
    }
    return 0;
}