数学、位运算、贪心、二分、交互

利用性质！利用性质！利用性质！利用性质！利用性质！利用性质！利用性质！

令答案为 $a,b,c$，钦定 $a < b < c$，根据 $a \operatorname{xor} b \operatorname{xor} c$ 的结果分讨。

• $a \operatorname{xor} b \operatorname{xor} c \neq 0$

由于 $a \neq b \neq c$，如果值域前缀 $[1,i]$ 中有至少一个数被拿走，这个前缀的异或和就非 $0$，可以二分得到 $a$ 的值。同理二分值域后缀 $[a+1,n]$ 得到 $c$ 的值，然后询问一次全局异或和得到 $a \operatorname{xor} b \operatorname{xor} c$ 的值，利用 $a,c$ 计算出 $b$。

• $a \operatorname{xor} b \operatorname{xor} c = 0$

看题解来的，无从下手。

由于 $a,b,c$ 的异或和为 $0$，如果 $a$ 的第 $k$ 个二进制位为 $1$，$b,c$ 中必定有且仅有一个数的第 $k$ 个二进制位为 $1$。该性质对 $b,c$ 同样有效。

又因为 $a < b < c$ 所以 $b,c$ 的最高二进制位相同，并且 $a$ 的这个二进制位为 $0$。

枚举 $a$ 的最高二进制位，设其为第 $i$ 个二进制位，找到最小的使得值域前缀 $[1,2^{i+1} - 1]$ 中的数异或和非 $0$ 的整数 $i$，这个非 $0$ 异或和即为 $a$ 的值。得到 $a$ 之后在区间 $[a+1,n]$ 二分出 $c$。注意可能不存在异或和为 $0$ 的值域前后缀，所以应当初始化 $a=1,c=n$。

时间复杂度 $O(\log n)$。

#include<bits/stdc++.h>
using namespace std;
long long n,a,c,sum;
long long ask(long long l,long long r){
    static long long ret;
    cout<<"xor"<<' '<<l<<' '<<r<<endl;
    cin>>ret;
    return ret;
}
void solution(){
    cin>>n,a=1ll,c=n,sum=ask(1,n);
    if(sum!=0){
        long long l=1ll,r=n;
        while(l<=r){
            long long mid=(l+r)>>1;
            if(ask(1ll,mid)) r=mid-1;
            else a=mid+1,l=mid+1;
        }
    }
    else{
        for(int i=0;i<=60;i++){
            a=ask(1ll,(1ll<<(i+1))-1);
            if(a!=0ll) break;
        }
    }
    long long l=a+1,r=n;
    while(l<=r){
        long long mid=(l+r)>>1;
        if(ask(mid,n)) l=mid+1;
        else c=mid-1,r=mid-1;
    }
    cout<<"ans"<<' '<<a<<' '<<(sum^a^c)<<' '<<c<<endl;
}
int T;
int main(){
    ios::sync_with_stdio(0);
    cin>>T;
    while(T--) solution();
    return 0;
}