CF1584D Guess the Permutation 题解

本文主要是介绍CF1584D Guess the Permutation 题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

CF1584D Guess the Permutation 题解

被薄纱了。

解法

考虑何时产生逆序对。在翻转两个不相交的区间后，原序列被分为四段，分别是 $[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, mi d]$ 中逆序对的个数，如果没有逆序对则表示 $\le i-1$ ，否则表示 $\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;
}