题解：CF2049E Broken Queries

ARIS2_0 · 2025-01-03 20:17:12 · 题解

思路

大力分讨。

下文称对区间 [l,r] 进行询问得到的值称为区间 [l,r] 的检验值。

设 mid_1=\frac{n}{2},mid_2=\frac{mid_1}{2}。

考虑将数组分为 3 部分：第一部分为 [1,mid_2]，第二部分为 [mid_2+1,mid_1]，第三部分为 [mid_1+1,n]。

设第 i 个部分的检验值为 val_i。

接下来进行分类讨论：

若 $val_3=1$，说明 $k>n-mid_1$，那么在 $[1,mid_1]$ 中找到一个最大的 $g$ 使得区间 $[g,n]$ 的检验值为 $0$，此时 $k=n-g+1$。 否则，在 $[1,mid_1]$ 中找到一个最小的 $g$ 使得区间 $[1,g]$ 的检验值为 $1$，此时 $k=g$。 $val_1\not=val_2$，此时 $1$ 不在第三部分内。 若 $val_3=0$，说明 $k>n-mid_1$，那么在 $[mid_1+1,n]$ 中找到一个最小的 $g$ 使得区间 $[1,g]$ 的检验值为 $0$，此时 $k=g$。 否则，在 $[mid_1+1,n]$ 中找到一个最大的 $g$ 使得区间 $[g,n]$ 的检验值为 $1$，此时 $k=n-g+1$。

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define debug1(x) cerr<<#x<<"="<<x<<" "
#define debug2(x) cerr<<#x<<"="<<x<<"\n"
const int inf=1e16;
int check(int l,int r){
    cout<<"? "<<l<<" "<<r<<endl;
    int pos;cin>>pos;
    return pos;
}
signed main(){
    // ios::sync_with_stdio(0);
    // cin.tie(0);
    int t;cin>>t;
    while(t--){
        int n;cin>>n;
        int mid1=n/2,mid2=mid1/2;
        int val1=check(1,mid2),val2=check(mid2+1,mid1),val3=check(mid1+1,n);
        int g=0,l=0,r=0,k=0;
        if(val1==val2){
            l=1;r=mid1;
            if(val3){
                while(l<=r){
                    int mid=(l+r)/2;
                    if(check(mid,n)==0)g=mid,l=mid+1;
                    else r=mid-1;
                }
                k=n-g+1;
            }
            else{
                while(l<=r){
                    int mid=(l+r)/2;
                    if(check(1,mid)==1)g=mid,r=mid-1;
                    else l=mid+1;
                }
                k=g;
            }
        }
        else{
            l=mid1+1;r=n;
            if(val3){
                while(l<=r){
                    int mid=(l+r)/2;
                    if(check(mid,n)==1)g=mid,l=mid+1;
                    else r=mid-1;
                }
                k=n-g+1;
            }
            else{
                while(l<=r){
                    int mid=(l+r)/2;
                    if(check(1,mid)==0)g=mid,r=mid-1;
                    else l=mid+1;
                }
                k=g;
            }
        }
        cout<<"! "<<k<<endl;
    }
    return 0;
}