题目链接：https://codeforces.com/contest/2037

E. Kachina's Favorite Binary String

通过不断询问$k_i=f(1,i),i=1,2,...,n$，如果ki>ki-1，则表示改位置为1，会产生新的满足条件的子串；如果$k_i=k_{i-1}$，则表示当前位置是0，不会产生新的满足条件的子串。在字符串最开始的位置如果为1的话，也不会产生新的子串，所以通过找到第一个不为零的$k_i$，其值为多少就表示在这个1前有多少个0，再结合其位置$i$就可以知道在最前面有多少个1了。

#include<bits/stdc++.h>
using namespace std;
int n,t;
int a[200005],k[200005];
int query(int l,int r)
{
    cout<<"? "<<l<<" "<<r<<endl;
    int x;
    cin>>x;
    return x;
}
int main()
{
	cin>>t;
    while (t--)
    {
        cin>>n;
        for (int i=0;i<=n;i++) 
        	a[i]=0;
        for (int i=2;i<=n;i++)
        	k[i]=query(1,i);
        if (k[n]==0) 
        {
            cout<<"! IMPOSSIBLE"<<endl;
            continue;
        }
        for (int i=2;i<=n;i++)
        	if (k[i]>k[i-1]) a[i]=1;
        for (int i=2;i<=n;i++)
        	if (a[i]!=0)
            {
                for (int j=1;j<=i-1-k[i];j++)
                	a[j]=1;
            }
        cout<<"! ";
        for (int i=1;i<=n;i++)
        	cout<<a[i];
        cout<<endl;
    }
}