题意
有一个未知的排列 $a$，其长度为 $n$，你通过进行不超过 $4n$ 次交互将排列排序。
- 给出 $l, r$，将 $a_l, a_{l + 1}, \ldots, a_r$ 翻转，即变成 $a_r, a_{r - 1}, \ldots, a_l$。操作完成后返回当前数组逆序对个数。
题解
考虑翻转 $\left[l, r\right]$ 对全局逆序对的影响。设：
- $v_1$ 表示 $\left[1, l - 1\right]$ 中的逆序对数量。
- $v_2$ 表示 $\left[l, r\right]$ 中的逆序对数量。
- $v_3$ 表示 $\left[r + 1, n\right]$ 中的逆序对数量。
- $v_4$ 表示左端点在 $\left[1, l - 1\right]$，右端点在 $\left[l, r\right]$ 中的逆序对数量。
- $v_5$ 表示左端点在 $\left[1, l - 1\right]$，右端点在 $\left[r + 1, n\right]$ 中的逆序对数量。
- $v_6$ 表示左端点在 $\left[l, r\right]$，右端点在 $\left[r + 1, n\right]$ 中的逆序对数量。
我们发现，变动的变量只有 $v_2$。新的 ${v_2}' = \binom{r - l + 1}2 - v_2$。
而当前逆序对数与原来的逆序对数之差 $cur - ori = \binom{r - l + 1}2 - 2 \cdot v_2$，由此我们可以通过两次询问算出 $\left[l, r\right]$ 中的逆序对数量并还原排列。
设 $inv_i$ 表示 $\left[1, i\right]$ 中的逆序对数。
令 $b_i = inv_i - inv_{i - 1}$，表示在 $\left[1, i - 1\right]$ 中，比 $a_i$ 大的数的数量。
得知 $b_i$ 之后，可以从后往前确认每个 $a_i$，然后通过 $n$ 次交换将 $a$ 排序。
总交互次数不超过 $3n$。
代码
struct VOIDENGINE {
int swp(int l, int r) {
cout << l + 1 << " " << r + 1 << endl;
return bin();
}
VOIDENGINE([[maybe_unused]] int TEST_NUMBER) {
int n; bin(n);
vi o(n);
vi s(n);
eu(i, n) {
s[i] = swp(0, i);
if (s[i] == 0) return;
o[i] = swp(0, i);
if (o[i] == 0) return;
}
vi inv(n);
eu(i, n) inv[i] = (o[i] - s[i] + i * (i + 1) / 2) / 2;
for (int i = n - 1; i > 0; --i) inv[i] -= inv[i - 1];
vi a(n); iota(ALL(a), 0);
set<int> all(ALL(a));
for (int i = n - 1; i >= 0; --i) {
auto it = all.rbegin();
eu(inv[i]) ++it;
a[i] = *it;
all.erase(*it);
}
eu(i, n) {
if (a[i] == i) continue;
eu(j, i + 1, n) {
if (a[j] != i) continue;
if (swp(i, j) == 0) return;
reverse(ALL(a, i, j));
break;
}
}
}
};
void VOIDSPECTRE([[maybe_unused]] int argc, [[maybe_unused]] char* argv[]) {
}