贪心、二分

有一个长度为 $n = 2^m$ 的 $\texttt{01}$ 序列，序列仅包含 $1$ 个 $\texttt{1}$，每次可以询问一个区间的和。

当询问的区间长度小于常数 $k$ 时将会返回正确答案；否则将返回错误答案。

交互库非自适应，序列信息和 $k$ 在询问开始前已经确定，使用至多 $33$ 次询问确定 $k$ 的值，$4 \leq n \leq 2^{30}$。

队友比我想得快，但至少我想出来了，令人感慨。

开局首先询问 $[1,\frac{n}{2}]$ 的区间和，由于 $[1,n]$ 中有一个 $1$，区间 $[\frac{n}{2} + 1,n]$ 的询问结果肯定和它不一样，于是通过一次询问得到了两个信息。

对于这两个长度为 $\frac{n}{2}$ 的区间，询问答案为 $1$ 的区间的两个子区间。

如果答案相同，那么 $1$ 不在这个区间中，同时由于区间本身的答案为 $1$ 可以断定 $k \leq \frac{n}{2}$，直接用这个区间二分 $k$ 的值，至多使用 $30$ 次询问。

如果答案不同，那么 $1$ 在这个区间中，同时 $k > \frac{n}{2}$，假设 $[\frac{n}{2} + 1,n]$ 的询问结果为 $1$ 并且 $1$ 在这个区间内，那么包含区间 $[\frac{n}{2} + 1,n]$ 的询问正确结果必为 $1$。在区间 $[1,\frac{n}{2}]$ 二分最大的使得 $[l,n]$ 询问的结果为 $0$ 的整数 $l$，至多使用 $30$ 次询问。

总询问数至多为 $3 + 30 = 33$ 次。

#include<bits/stdc++.h>
using namespace std;
long long n,ans;
int ask(int l,int r){
    static int ret;
    cout<<'?'<<' '<<l<<' '<<r<<endl;
    cin>>ret;
    return ret;
}
void solution(){
    cin>>n,ans=0ll;
    if(ask(1,n/2)){
        if(ask(1,n/4)!=ask(n/4+1,n/2)){
            long long l=n/2+1,r=n;
            while(l<=r){
                long long mid=(l+r)>>1;
                if(ask(1,mid)) l=mid+1;
                else ans=mid,r=mid-1;
            }
        }
        else{
            long long l=1ll,r=n/2;
            while(l<=r){
                long long mid=(l+r)>>1;
                if(ask(1,mid)) ans=mid,r=mid-1;
                else l=mid+1;
            }
        }
    }
    else{
        if(ask(n/2+1,n/4*3)!=ask(n/4*3+1,n)){
            long long l=1ll,r=n/2;
            while(l<=r){
                long long mid=(l+r)>>1;
                if(ask(mid,n)) r=mid-1;
                else ans=mid,l=mid+1;
            }
        }
        else{
            long long l=n/2+1,r=n;
            while(l<=r){
                long long mid=(l+r)>>1;
                if(ask(mid,n)) ans=mid,l=mid+1;
                else r=mid-1;
            }
        }
        ans=n-ans+1;
    }
    cout<<'!'<<' '<<ans<<endl;
}
int T;
int main(){
    ios::sync_with_stdio(0);
    cin>>T;
    while(T--) solution();
    return 0;
}