题解：P7015 [CERC2013] Crane

· · 题解

感觉像诈骗题，一开始把所有排序全部想了一遍，从冒泡到归并，结果发现不符合题目要求 /kel。

我们需要把排列排成 1 到 n 的顺序，每次操作可以选一个偶数长度的连续区间，把前半段和后半段交换。

一个很自然的想法是从左往右依次把数字 1, 2, \cdots,n 放到正确位置。处理数字 x 时，假设位置 1 到 x - 1 已经固定好了，以后再也不碰它们。

设数字 x 当前在位置 p（显然 p \ge x）。如果 p = x，不用管它；否则我们需要把 x 往左移动。每次操作我们选一个区间，让 x 作为区间的最后一个元素，交换前后两半后，x 会向左移动区间长度的一半。

关键是怎么选这个区间：设距离 d = p - x，取 k = \lceil \frac{d}{2} \rceil，区间左端点 l = p - 2k + 1，右端点 r = p。这样区间长度正好是 2k，x 在区间最后一位，交换后 x 会向左移动 k 格。

新的距离变成 d' = d - k = \lfloor \frac{d}{2} \rfloor，也就是说每次操作至少把距离减半。因为距离最多 n - 1，每个数字最多操作 \lceil \log_2 n \rceil 次，n \le 10^4 时总操作数不到 1.4 \times 10^5，远小于 5 \times 10^5。

这时候有人问了，为什么不会破坏已经固定的前缀？关键在于构造保证了 l \ge x，所以位置 1 到 x - 1 永远不会被碰到。

实际操作时，每次交换就是做 k 对元素交换，同时更新每个数字的位置数组。

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ull = unsigned long long;

const int kMaxN = 3e5 + 10;

ll n, a[kMaxN], pos[kMaxN];
vector<pair<ll, ll>> ans;

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int t;
  for (cin >> t; t; -- t) {
    fill(pos + 1, pos + n + 1, 0);
    ans.clear();
    cin >> n;
    for (int i = 1; i <= n; ++ i) {
      cin >> a[i], pos[a[i]] = i;
    }
    for (int x = 1; x <= n; ++ x) {
      for (ll p, d, k, l, r; pos[x] > x; ) {
        p = pos[x], d = p - x, k = (d + 1) / 2, l = p - 2 * k + 1, r = p;
        ans.push_back({l, r});
        for (int t = 0, i, j, u, v; t < k; ++ t) {
          i = l + t, j = l + k + t, u = a[i], v = a[j];
          swap(a[i], a[j]);
          pos[u] = j, pos[v] = i;
        }
      }
    }
    cout << ans.size() << '\n';
    for (auto i : ans) {
      cout << i.first << ' ' << i.second << '\n';
    }
  }
  return 0;
}