题解：P12552 嘟嘟嘟

· · 题解

有个结论：随机排列的严格前缀 \max 数量级为 O(\log n)，证明显然。

由于交互器非自适应，考虑初始随机一个区间，随机顺序判断一个点能否更新这个区间（替换区间端点），以保证这个区间含括当前所有已处理点。

先判断当前点是否属于区间，操作 O(n) 次。假如需要更新，再询问一次即可，由上面结论可知这是 O(\log n) 次的。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=50005;
ll n,p[N],s,t;
int main(){
    mt19937 rnd;srand(time(0));rnd.seed(rand());
    scanf("%lld",&n);
    for(ll i=1;i<=n;i++) p[i]=i;
    for(ll i=2;i<=n;i++) swap(p[i],p[rand()%(i-1)+1]);
    s=p[1],t=p[2];
    for(ll i=3,x;i<=n;i++){
        printf("? %lld %lld %lld\n",s,t,p[i]);fflush(stdout);scanf("%lld",&x);
        if(x==0){
            printf("? %lld %lld %lld\n",s,p[i],t);fflush(stdout);scanf("%lld",&x);
            if(x) t=p[i]; else s=p[i];
        }
    }
    printf("! %lld %lld\n",s,t);fflush(stdout);
    return 0;
}