P7109 滴水不漏

美妙的交互题。
下列题解讲的很清楚阿：

最后再附上一个我打了注释的程序吧$qwq$

#include <bits/stdc++.h>
#define ll int
#define maxn 1111
using namespace std;
ll n,a[maxn],fg,tp,sum[maxn];
ll ns,ls,k,as;

inline ll tot(ll x){
    return (x*(x+1))/2;
}

inline int ask(ll x,ll y){
    printf("? %d %d\n",x,y);
    cout.flush();
    int ln;
    scanf("%d",&ln);
    return ln;
}

int main(){
    scanf("%d",&n);
    as=ask(1,1);
    k=ns=ls=0;
    if(as)      sum[1]=1,ns=1,k=2;
    else        sum[1]=0,ns=0,k=1;
    if(n==1){
        printf("! %d\n",sum[1]);
        cout.flush();
        return 0;
    }//特判1的情况
    for(register int i=2;i<=n;++i){
        while(k<i){//将i中的水依次倒入k,k+1,...
            if(ask(i,k))//如果k倒满了，nowsum为现在前k个水桶的水量总和，k更新，更新后的k值为0    
                ns=tot(k),++k,ls=0;
            else//如果不满，可以跳出了
                break;
        }
        if(k==i+1){//如果一直倒到了i+1
            sum[i]=ns;//前i个水桶都是满的，水量总共为现在倒满了的水量
            continue;//处理下一个水桶
        }
        if(ask(k,k)){//如果k为i（或者更小），倒满
            ++k,ns=tot(k-1),sum[i]=ns;
            //更新k，现在所有满了的水桶的总水量为更新前的k（即现在的k-1），前i个的所有值为nowsum
            continue;//直接处理下一个水桶
        }
        ll l=1,r=k-1,pos=0;//k此时并没有倒满，尝试在1~(k-1)中寻找
        while(l<=r){
            ll mid=(l+r)>>1;
            if(ask(mid,k))//如果将mid的水量全部倒入k，k倒满了
                pos=mid,r=mid-1;//向下界寻找
            else    
                l=mid+1;//否则向上界寻找
            ask(k,mid);//撤回操作（方便后面的寻找）
        }
        if(!pos)//如果并没有找到pos的话
            ls=0;//a[k]里面并没有任何水，即k-1个桶中是满的而k桶是空的
        else    
            ls=k-pos;//否则就可以愉快的求出k中的水量了
        sum[i]=ns+ls;//此时1～i中的总水量为灌满了水的桶的总水量和第k个桶的总水量
        //循环结束，此时1～(k-1)中的水一定是满的，k可满可不满
        //在求每一个桶的时候，将其分为两部分求：
        //先通过往前面没有水（或者不满的k）中倒来确定1～i中的所有水一共可以填满多少个水桶，
        //再通过二分求出多余的那部分水到底是多少，最终一定可以确定前缀和数组的值
    }
    printf("! ");
    for(register int i=1;i<=n;++i)
        printf("%d ",sum[i]-sum[i-1]);//前缀和求出每一个桶中的原有水量
    cout.flush();
    return 0;
}