F2. Guess the K-th Zero (Hard version)

方法一：
记忆化二分，有这么两种二分：、
第一种和线段树的所有区间重叠，的子区间都是，如果开个桶去记忆化，需要查次，但可以知道的是被遍历的区间远小于这么多，所以可以去记忆化。

方法二：
将扩大到的幂次，然后预处理的幂次的下标的值（即对原数组分块）。然后每次二分答案在那个块里面（已经预处理，不需要询问测评姬），接着只要在长度不大与的块里面二分询问就可以了。找到答案后用树状数组维护的值增加的值。

MyCode:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
map<pair<int,int>,int>mp;
void add(int l,int r,int x) {
    --mp[{l,r}];
    if(l==r) return;
    int mid=(l+r)>>1;
    if(x<=mid) add(l,mid,x);
    else add(mid+1,r,x);
}
int main() {
    int n,t,k;
    cin>>n>>t;
    while(t--) {
        cin>>k;
        int l=1,r=n,mid,x;
        while(l<r) {
            mid=(l+r)>>1;
            if(!mp.count({l,mid})) {
                cout<<"? "<<l<<' '<<mid<<endl;
                cin>>x;
                mp[{l,mid}]=mid-l+1-x;
            }
            x=mp[{l,mid}];
            if(k<=x) r=mid;
            else {
                l=mid+1;
                k-=x;
            }
        }
        cout<<"! "<<r<<endl;
        add(1,n,r);
    }
    return 0;
}