CF1584D

vp 时候搞出来的 $\le\log n+2+?$ 次询问做法。看了一圈没有做法跟我相同的，为什么呢。

首先看到 $40$ 次猜测是一次二分的 $\log$ 加上常数。然后发现，如果我们找到了 $j$，又知道 ? 1 n 和 ? 1 j-1 的结果，就可以解出来 $i,k$。于是想怎么二分。

设当前二分到 $mid$，我们先询问 $[1,mid]$ 得到 $x$，然后开始分讨：

• $x=0$ 则 $j>mid$。

• $x$ 等于询问 $[1,n]$ 的答案则 $j<mid$。

• $\exists k,x=\binom{k}{2}$，此时是都有可能的，于是再询问 $[1,mid+1]$ 得到 $y$，分情况：

• $\exists m,y=\binom{m}{2}\land m=k+1$，则一定有 $j<mid$，因为 $mid+1$ 显然仍在第一段区间内。

• $y=x$ 则容易发现，一定有 $mid+1=j$，否则会有 $y>x$。

• 否则 $mid>j$。

但是这样询问次数可能去到 $2\log n$。考虑怎么样节省一点。发现如果出现过上述第三种情况的第一种小情况，则可以记录一个位置，并且以后根据记录的这个位置就可以判断出是否还在第一段。

对于第二种小情况，遇到了可以直接 break。第三种情况大概猜测会分散在不同位置，遇到概率不大，不会造成多少次额外的询问。

于是就是 $\log n+2+?$ 次解决了。

code：

int n,m;
il ll ask(int l,int r){
	printf("? %d %d\n",l,r);
	fflush(stdout);
	ll x;read(x);
	if(x==-1){
		exit(0);
	}
	return x;
}
il bool check(ll x){
	ll y=sqrt(x*2)+1;
	return x==y*(y-1)/2;
}
void Yorushika(){
	read(n);
	ll s=ask(1,n);
	int l=1,r=n,ans=0;
	int p=0,x=0;
	while(l<=r){
		int mid=(l+r)>>1;
		ll tmp=0;
		if(check(tmp=ask(1,mid))){
			if(!tmp){
				ans=mid,l=mid+1;
				continue;
			}
			ll z=sqrt(tmp*2)+1;
			if(p){
				if(z==x+mid-p){
					ans=mid,l=mid+1;
				}else{
					r=mid-1;
				}
			}else{
				ll tmpp;
				if(mid<n&&tmp!=s&&(tmpp=ask(1,mid+1))==(z+1)*z/2){
					ans=mid,l=mid+1;
					p=mid,x=z;
				}else{
					if(tmpp==tmp&&tmp!=s){
						ans=mid;
						break;
					}
					r=mid-1;
				}
			}
		}else{
			r=mid-1;
		}
	}
	ll tmp=ask(1,ans);
	ll u=sqrt(tmp*2)+1;
	tmp=s-tmp;
	ll v=sqrt(tmp*2)+1;
	printf("! %lld %d %lld\n",ans-u+1,ans+1,ans+v);
	fflush(stdout);
}
signed main(){
	int t=1;
		 read(t);
	while(t--){
		Yorushika();
	}
}