QOJ #4424. Babushka and her pierogi 题解

Description

给定 $n,C$ 和两个排列 $a_1,a_2,\ldots,a_n$ 和 $b_1,b_2,\ldots,b_n$，每次可以用 $|a_i-a_j|+C$ 的代价交换 $a_i$ 和 $a_j$。问将序列从 $a$ 变成 $b$ 的最小代价。

$n\leq 10^6$。

Solution

先连 $a_i\to b_i$，每次相当于是交换两个点的出边。

交换次数的下界是 $n$ 减置换环数量，$|a_i-a_j|$ 这个权值的下界是 $\sum|a_i-b_i|$，容易发现这两个都能取到下界。

考虑怎么证明这件事情。

首先每次交换的两个位置一定满足 $b_j\leq a_i\leq a_j\leq b_i$，且在同一置换环中，否则一定会浪费。

设 $pre_{b_i}=a_i,nxt_{a_i}=b_i$，考虑找到当前最小的数 $x$，每次操作 $x$，直到 $nxt_x=x$。我们相当于是要找到一个 $y$，使得 $x\leq y\leq pre_x\leq nxt_y$。

不妨设 $x$ 所在的置换环中有 $c$ 个在 $[x,pre_x-1]$ 之间的数，那么这 $c$ 个数有 $c$ 个出边，而在 $[x,pre_x-1]$ 的入边最多只有 $c-1$ 个，因为 $pre_x$ 不在这个范围内。所以一定能找到这样的 $y$ 进行操作。

暴力跳 $nxt$ 找 $y$ 的复杂度是 $O(n^2)$，过不了，考虑优化。

这里的技巧是从 $x$ 同时跳 $pre$ 和 $nxt$ 找 $y$，则找到 $y$ 的次数为 $O(环长/2)$，进一步会发现次数为当前的环分裂后的较小的环长。根据启发式分裂的思想，这个东西的总复杂度就是 $O(n\log n)$。

时间复杂度：$O(n\log n)$。

Code

#include <bits/stdc++.h>

#define int int64_t

const int kMaxN = 2e5 + 5;

int n, c, cost;
int a[kMaxN], b[kMaxN], unq[kMaxN], pos[kMaxN], pre[kMaxN], nxt[kMaxN];
std::vector<std::pair<int, int>> vec;

void work(int x, int y) {
  int i = pos[x], j = pos[y];
  cost += abs(unq[a[i]] - unq[a[j]]) + c;
  int a1 = x, b1 = nxt[x], a2 = y, b2 = nxt[y];
  std::swap(a[i], a[j]);
  std::swap(pos[x], pos[y]);
  nxt[a1] = b2, pre[b2] = a1;
  nxt[a2] = b1, pre[b1] = a2;
  vec.emplace_back(i, j);
}

void discrete() {
  std::sort(unq + 1, unq + 1 + n);
  for (int i = 1; i <= n; ++i) {
    a[i] = std::lower_bound(unq + 1, unq + 1 + n, a[i]) - unq;
    b[i] = std::lower_bound(unq + 1, unq + 1 + n, b[i]) - unq;
    nxt[a[i]] = b[i], pre[b[i]] = a[i];
    pos[a[i]] = i;
  }
}

void dickdreamer() {
  std::cin >> n >> c;
  cost = 0, vec.clear();
  for (int i = 1; i <= n; ++i) {
    std::cin >> a[i] >> b[i];
    unq[i] = a[i];
  }
  discrete();
  for (int i = 1; i <= n; ++i) {
    for (; pre[i] != i;) {
      // std::cerr << i << ' ' << pre[i] << '\n';
      for (int x = i, y = i;; x = pre[x], y = nxt[y]) {
        if (x <= pre[i] && nxt[x] >= pre[i]) {
          work(pre[i], x);
          break;
        }
        if (y <= pre[i] && nxt[y] >= pre[i]) {
          work(pre[i], y);
          break;
        }
      }
    }
  }
  std::cout << cost << ' ' << vec.size() << '\n';
  for (auto [x, y] : vec) std::cout << x << ' ' << y << '\n';
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}