这是一个交互题！
题目链接 --> Problem - D - Codeforces
题目大意
这是一个交互题！
给定一个长度为 \(n\) 的自然排列，但其中 \([i,j-1],[j,k]\)两部分被翻转了。
你可以进行如下询问：
- 给出 \([l,r]\) ，回答 \([l,r]\) 这一段的逆序对数量。
询问次数不超过40次，其中 \((n <= 10^9, i < j-1,j < k)\)
分析
-
我们可以先通过二分得到 \(i\)，即找到满足 \([1,x]\) 中逆序对等于 \(0\) 的最大数 \(x\)
-
这一步的时间复杂度为 \(O(log(n))\)，大约 \(log_2(10^9)=30\) 次询问
-
然后我们观察 \([i, n]\) 和 \([i+1,n]\) 这两段区间的逆序对差值
举个例子，对于下面这个自然排列
\[1, 2, 3, 4, 5, 6, 7, 8, 9, 10 \]假设 \(i = 2, j = 5, k= 8\)，则反转后的排列为
\[1, 4, 3, 2, 8, 7, 6, 5, 9, 10 \]-
\([i, n]\) （即 \([2, 10]\) ）的逆序对数量为 \(2 + 1\)
-
\([i+1, n]\) （即 \([3, 10]\) ）的逆序对数量为 \(1\)
实际上，\([i,n]\) 和 \([i+1,n]\) 的逆序对之差围为 \(j-1-i\)
同理，\([j,n]\) 和 \([j+1,n]\) 的逆序对之差为\(k - j\)
所以我们只需要 \(log(n)+4\) 次询问即可得出答案
Code
这是一个交互题！
il int ask(int x, int y) {
cout << "? " << x << " " << y << endl;
int ans; cin >> ans;
return ans;
}
void solve() {
cin >> n;
int l = 1, r = n;
// 二分 i 的位置
while (l < r) {
int mid = (l + r + 1) >> 1;
if (ask(1, mid) == 0) l = mid;
else r = mid - 1;
}
int i = l;
int j = i + ask(i, n) - ask(i + 1, n) + 1;
int k = j + ask(j, n) - ask(j + 1, n);
cout << "! " << i << " " << j << " " << k << endl;
return;
}