被薄纱了。

解法

考虑何时产生逆序对。在翻转两个不相交的区间后，原序列被分为四段，分别是 $[1,i-1],[i,j-1],[j,k],[k+1,n]$。

每一段中数都是单调的，分别是单调递增，单调递减，单调递减，单调递增。只有中间两段内部有逆序对，个数分别是 $\dfrac{(j - i) \times (j - i - 1)}{2},\dfrac{(k - j + 1) \times (k - j)}{2}$。我们询问 $[1,n]$ 中逆序对的个数等价于询问 $[i,k]$ 中逆序对的个数。

我们二分确定 $i$ 的值，即每次询问 $[1,mid]$ 中逆序对的个数，如果没有逆序对则表示 $mid \le i-1$，否则表示 $mid \ge i$。

下一步确定 $j$ 的值。我们可以询问 $[i,n]$ 中逆序对的个数，这等价于询问 $[i,k]$ 中逆序对的个数。我们再询问 $[i+1,n]$ 中逆序对的个数。根据上面的推导，设 $[i,n]$ 中逆序对的个数为 $x_1$，$[i+1,n]$ 中逆序对的个数为 $x_2$，则 $x_1 - x_2 = \dfrac{(j - i) \times (j - i - 1)}{2} - \dfrac{(j - i - 1) \times (j - i - 2)}{2} = j - i - 1$。因为我们已经确定了 $i$ 的值，所以即可确定 $j$ 的值。

类似于 $j$，我们可以确定 $k$ 的值。我们可以询问 $[j,n]$ 中逆序对的个数和 $[j+1,n]$ 中逆序对的个数。设 $[j,n]$ 中逆序对的个数为 $x_1$，$[j+1,n]$ 中逆序对的个数为 $x_2$，则 $x_1 - x_2 = \dfrac{(k - j + 1) \times (k - j)}{2} - \dfrac{(k - j) \times (k - j - 1)}{2} = k - j$。

在二分过程中，我们最多询问 $\lceil \log_2 10^9 \rceil = 30$ 次确定 $i$，再用 $4$ 次确定 $j,k$。所以一定在 $40$ 次以内。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
int t,n,l,r,mid,tmp,i,j,k,xx1,xx2;
inline void ask(const int &l,const int &r) noexcept
{
    printf("? %d %d\n",l,r),fflush(stdout);
}
signed main()
{
    scanf("%lld",&t);
    while(t--)
    {
        scanf("%lld",&n);
        l=1,r=n;
        while(l<=r)
        {
            mid=(l+r)/2,ask(1,mid),scanf("%lld",&tmp);
            if(tmp==0) l=mid+1;
            else r=mid-1;
        }
        i=l-1;
        ask(i,n),ask(i+1,n),scanf("%lld %lld",&xx1,&xx2);
        j=xx1-xx2+i+1;
        ask(j,n),ask(j+1,n),scanf("%lld %lld",&xx1,&xx2);
        k=xx1-xx2+j;
        printf("! %lld %lld %lld\n",i,j,k),fflush(stdout);
    }
    return 0;
}