Codeforces 1584D. Guess the Permutation

传送门

题目大意

交互题，有一个长度为 \(n(4\leq n\leq 10^9)\) 的序列 \(a,a_i=i\) ，有三个值 \(i,j,k(1\leq i，改序列将区间 \([i,j-1]\) ， \([j,k]\) 分别翻转。现在每次询问可以查询序列一段区间 \([l,r]\) 内的逆序对数，需要在 \(40\) 次询问内求出序列的 \(i,j,k\) 。

思路

三个数字都可以二分求得，但询问次数仅允许我们进行一次二分，于是我们可以选择二分求出 \(i\) ，也就是 \([1,x]\) 中第一个使逆序对数为 \(0\) 的 \(x\) 。之后考虑通过 \(i\) 来求出 \(j\) 和 \(k\) ，我们可以询问 \([i,N]\) ，与 \([i+1,N]\) ，不难发现两次询问所得到的逆序对的数量的差就是第一个被反转的区间的长度 \(-1\) ，于是就可以得到 \(j\) ，同理可以由 \(j\) 得到 \(k\) 。

代码

#include
#include
#include
using namespace std;
using LL = long long;
using ULL = unsigned long long;
using PII = pair;
using TP = tuple;
#define all(x) x.begin(),x.end()
#define pb push_back
#define mk make_pair
#define int LL
//#define lc p*2
//#define rc p*2+1
//#define endl '\n'
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
//#pragma warning(disable : 4996)
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
const double eps = 1e-8;
const LL MOD = 1000000007;
const LL mod = 998244353;
const int maxn = 200010;

int T, N;

bool Check(int x)
{
	int ans;
	cout << "? " << 1 << ' ' << x << endl;
	cin >> ans;

	return !ans;
}

void solve()
{
	int i, j, k;
	int lo = 1, hi = N + 1;
	while (hi - lo > 1)
	{
		int mid = (hi + lo) / 2;
		if (Check(mid))
			lo = mid;
		else
			hi = mid;
	}
	i = lo;
	int x, y, a, b;
	cout << "? " << i << ' ' << N << endl;
	cin >> x;
	cout << "? " << i + 1 << ' ' << N << endl;
	cin >> y;
	j = i + x - y + 1;
	cout << "? " << j << ' ' << N << endl;
	cin >> a;
	cout << "? " << j + 1 << ' ' << N << endl;
	cin >> b;
	k = j + a - b;
	cout << "! " << i << ' ' << j << ' ' << k << endl;
}

signed main()
{
	IOS;
	cin >> T;
	while (T--)
	{
		cin >> N;
		solve();
	}

	return 0;
}