本文共 1871 字，大约阅读时间需要 6 分钟。

思路：先分块，再块中二分。暴力修改400ms

#include<iostream>#include<vector>#include<queue>#include<cstring>#include<cmath>#include<map>#include<set>#include<cstdio>#include<algorithm>#define debug(a) cout<<#a<<"="<<a<<endl;using namespace std;const int maxn=2e5+1000;typedef int LL;inline LL read(){LL x=0,f=1;char ch=getchar();	while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}return x*f;}struct P{   LL l,r,sum;}block[maxn];LL ask(LL l,LL r){   cout<<"? "<<l<<" "<<r<<endl;   LL num;cin>>num;   cout.flush();   return num;}bool check(LL mid){     LL res=block[mid].r;///区间长度     LL num=res-block[mid].sum;///0的总数     return num;}int main(void){   cin.tie(0);std::ios::sync_with_stdio(false);   LL n,t;cin>>n>>t;   LL p=20;   LL cnt=(n+p-1)/p;///要分成的总块数   bool flag=1;   while(t--){      LL pos;cin>>pos;      if(flag==1){         flag=0;         for(LL i=1;i<=cnt;i++){             LL l=(i-1)*p+1;             LL r=(i)*p;             block[i].l=l;block[i].r=min(r,n);             block[i].sum=ask(1,min(r,n));///记录块的前缀和         }      }      LL l=1;LL r=cnt;//      while(l<r){//          LL mid=(l+r)>>1;//          if(check(mid)>=pos){///1到mid的0的个数//             r=mid;//          }//          else l=mid;//      }      LL choice=l;      for(LL i=l;i<=r;i++){          LL res=block[i].r;///1~r的区间长度          LL num1=block[i].sum;///1~i块的区间1数量          if(res-num1>=pos){             choice=i;             break;          }      }      ///choice此时为找到的块      LL L=block[choice].l;LL R=min(n,block[choice].r);      while(L<R){            LL mid=(L+R)>>1;            LL num=ask(1,mid);///1的个数            LL cnt=(mid-num);///1~mid的0的个数            if(cnt>=pos) R=mid;            else L=mid+1;      }      cout<<"! "<<L<<endl;      cout.flush();      ///暴力修改      for(LL i=choice;i<=cnt;i++){          block[i].sum++;      }   }   return 0;}