题解：P15551 Get MiN? Get MeX! 加强版

· · 题解

我们当然希望能直接用二分找出来 0 在哪。但是很可惜，在第一个询问中，我们并不知道返回的是 \min 还是 \operatorname{mex}。因此二分是没啥前途的。

不妨三分。对于当前三个段 a,b,c，我们尝试判断哪一段中一定没有 0，并将其删去。容易发现，肯定存在一个 k>0，使得 k 在一段中出现，[0,k) 的所有数在另一段出现。此时这对两段查询获得的值是相等的，而另一个区间的值一定与这两个不同。把唯一一个不同的段删去即可。进一步地，假设有 a=b，那么 c 取的一定是 \min，于是有 a=b<c。因此问两个区间即可确定是哪两个相等。

直接三分肯定是不行的，因为我们可能会把区间剁开，导致无法询问。所以采用另一种方法：选择当前两个区间中最大的一个剁成两半。这样区间总长最多两次划分就变为一半。划分到最后会剩下两个长度恰好为 1 的区间，用一次询问 2 即可确定到底哪个是 0。

每次询问我们只需要知道两个区间的答案，因此直接做就是 4\lceil\log_2 n\rceil。进一步地，除了第一次划分以外，每次都必然有恰好一个区间的答案是之前问过的。复用即可，总询问次数为 2\lceil\log_2 n\rceil+1，可以通过。

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
inline int query(int l,int r){
    cout<<"? 1 "<<l<<" "<<r<<endl;
    int res;return cin>>res,res;
}
int n;
int main(){
    cin>>n;if(n==1)return cout<<"! 1"<<endl,0;
    int l1=1,r1=n>>1,w1=-1,l2=r1+1,r2=n,w2=-1;
    for(;;){
        if(l1==r1&&l2==r2)break;
        if(r1-l1<r2-l2)swap(l1,l2),swap(r1,r2),swap(w1,w2);
        int mid=l1+r1>>1;
        if(!~w2)w2=query(l2,r2);
        int x=query(l1,mid);
        if(x==w2)w1=x,r1=mid;
        else if(x>w2)w1=w2,l1=mid+1;
        else w1=w2=x,l2=mid+1,r2=r1,r1=mid;
    }
    cout<<"? 2 "<<l1<<" "<<r1<<endl;
    int x;cin>>x,cout<<"! "<<(x==1?l2:l1)<<endl;
    return 0;
}