题解：AT_arc225_e [ARC225E] Gap Swap (hard)

DrDuck · 2026-07-23 15:35:42 · 题解

星图铺就的，未必是归途。但有人循着它，便不算迷路。

下面定义一个数 p_i 的「归宿」为位置 p_i，即这个数最终处于的位置。

:::info[书接上回] 以下为本人简单版本的题解。

先说结论，答案等于：

下面定义有效交换为对数对 (i,j),i<j 满足 p_i > i,p_j < j，且 \forall k \in (i,j),p_k = k 的交换操作。

如果数列非有序时任意有效交换一定存在，那么不断进行有效交换，每个数 p_i 都会趋近于自己的「归宿」，且总路程恰等于 |i-p_i|。

下面证明有效交换一定存在。

假设不存在有效交换，说明不存在数对 (i,i+1) 满足 p_i > i,p_{i+1}<i+1，即不存在数对满足 p_i > p_{i+1}，说明数列有序，与数列非有序矛盾。 :::

先说结论，答案等于：

我们尝试对一次有效交换 (i,j)（定义见上面的折叠框）进行分析。

对于 \sum_{i=1}^n |i - p_i| 这一项，我们发现 p_i 离他的「归宿」变近了 j-i 的距离，p_j 也离他的「归宿」变近了 j-i 的距离，那么这一项将会减小 2 \times(j-i)。

对于 \sum_{i=1}^n \sum_{j=i+1}^n [p_i > p_j] 这一项，由于 \forall k \in (i,j),p_i \ne k，则 \forall k \in (i,j),p_i>p_k，因此交换后 p_i 与 p_k 间的逆序对数量会减少 j - i - 1；同理，交换后 p_j 与 p_k 间的逆序对数量也会减少 j - i - 1，再加上 (p_i,p_j) 这一对逆序对被消去，减少的逆序对数量为 2 \times (j - i) - 1。

而最后两项都会归于零。

因此有一个重大发现：两项的差值就是我们的操作次数！因为我们倒着考虑所有操作的话，每进行一次操作，前一项就会比后一项多 1。

:::success[CODE]

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 5e+5 + 5;
int n;
int a[maxn];
struct BIT {
    int a[maxn];
    inline int lowbit(int x) {
        return x & -x;
    }
    inline void add(int x, int y) {
        for (int i = x; i <= n; i += lowbit(i)) a[i] += y;
    }
    inline int sum(int x) {
        int res = 0;
        for (int i = x; i; i -= lowbit(i)) res += a[i];
        return res;
    }
}t;
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        ans += abs(a[i] - i);
    }
    for (int i = n; i; i--) {
        ans -= t.sum(a[i]);
        t.add(a[i], 1);
    }
    cout << ans;
    return 0;
}

:::

欢迎找错，欢迎 hack。