CF1584D Guess the Permutation 题解

CF1584D Guess the Permutation 题解

被薄纱了。

解法

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

每一段中数都是单调的，分别是单调递增，单调递减，单调递减，单调递增。只有中间两段内部有逆序对，个数分别是 $\frac{(j-i)\times (j-i-1)}{2},\frac{(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=\frac{(j-i)\times (j-i-1)}{2}-\frac{(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=\frac{(k-j+1)\times (k-j)}{2}-\frac{(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;
}