题意：
交互题，t组样例。给出序列的长度n，将序列选择了三个位置i , j , k，翻转序列中的[ i , j − 1 ]。每次可以询问一段区间里逆序对的个数，在最多40次询问里求出i , j , k.
思路：
区间左端点固定时，移动右端点得到的逆序对个数是非递减的。而且在区间[ 1 , i ]的逆序对个数为0，后续区间一定不为0，这样就可以二分查找出i的位置p o s i。
接下来看如何确定j jj的位置p o s j。思考一下区间[ i , j − 1 ]的逆序对变化。假设区间为[ 6 , 5 , 4 , 3 , 2 ]，那么区间[ 1 , 5 ]的逆序对比区间[ 2 , 5 ]的逆序对多了4个，也就是除了第一个数外还有4个数。所以求出区间[ i , n ]和区间[ i + 1 , n ]的逆序对差值x ，p o s j − 1 = x + p o s i，p o s j = p o s j − 1 + 1，x+posi+1;
同理，也可以这样确定k的位置。
交互次数，确定i ii的位置最多要用到l o g ( 1 e 9 ) = 32次，确定j , k的位置用了2次，最多用34次。
参考博客
代码：
// Problem: D. Guess the Permutation // Contest: Codeforces - Codeforces Round #755 (Div. 2, based on Technocup 2022 Elimination Round 2) // URL: https://codeforces.com/contest/1589/problem/D // Memory Limit: 256 MB // Time Limit: 1000 ms // // Powered by CP Editor (https://cpeditor.org) #include<bits/stdc++.h> using namespace std; typedef long long ll;typedef unsigned long long ull; typedef pair<ll,ll>PLL;typedef pair<int,int>PII;typedef pair<double,double>PDD; #define I_int ll inline ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;} #define read read() #define rep(i, a, b) for(int i=(a);i<=(b);++i) #define dep(i, a, b) for(int i=(a);i>=(b);--i) ll ksm(ll a,ll b,ll p){ll res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;} ll qask(int l,int r){ cout<<"? "<<l<<" "<<r<<endl; cout.flush(); ll t=read; return t; } int main(){ int _=read; while(_--){ ll n=read; ll l=1,r=n,ans1=-1; while(l<=r){//二分查找i的位置 ll mid=(l+r)/2; ll now=qask(1,mid);//找下标最大的等于0的位置 if(now>0) r=mid-1;//说明答案在左边，移动右端点将区间向左边扩 else l=mid+1,ans1=mid;//答案已经合法，找还有没有更大的值 } // ll t=qask(ans1,n)-qask(ans1+1,n); ll ans2=t+1+ans1;//确定j的位置 第一个翻转的区间是[i,j-1] t=qask(ans2,n)-qask(ans2+1,n); ll ans3=t+ans2;//确定k的位置，第二个翻转的区间是[j,k] cout<<"! "<<ans1<<" "<<ans2<<" "<<ans3<<endl; } return 0; }
