题目描述

你需要分析排序算法，将 $n$ 个互不相同的整数，通过交换两个相邻的元素使得数列有序的 最少交换次数。
比如，原数列为： $9,1,0,5,4$ 排序后的数列为： $0,1,4,5,9$。

样例

输入格式
第一行一个整数 $n(n\leq500000)$。
接下来 $n$ 行，每行一个整数 $a_i(a_i\leq10^9)$。

5
9
1
0
5
4

输出格式
输出一个整数，表示操作次数。

6

算法与数据结构

树状数组
离散化

题解

这是一道用树状数组做的题，还要用到离散化的技巧。

一次有效的交换意味着什么呢？

为了使序列有序，一次有效的交换应该是后一个较小的数与他前一个较大的数交换，那么单独一个数字的交换次数，应该是这个数字前面比它大的数字的个数。

换句话说，当一个数字出现的时候，出现在它左边且比它大的数字的个数，就是当出现到这个数字为止（这个数字右边的数字还没出现）时，这个数字要到正确位置上交换的次数。

对每一个位置上的数字累加这样的次数，就是答案。

更一般的，令初始 sum = 0，对于第 i 个数字，出现在它左边且比它大的数字的个数如果是 x，就令 sum += x，遍历所有的数字，最后得到的累加和，就是答案。

现在剩一个问题：怎么知道出现在左边的、比自己大的数字有多少？
对于遍历到的第 i 个数字（记为 x），如果在遇到它的时候，单点更新树状数组 change(x)，改变的动作是加 1，即计数，即令 x 出现的次数加 1，那么，对于 getSum(x) 操作，就是求出从 1 到 x 的数字一共出现了多少次，即，不小于 x 的数字有多少个。

当我们得知了这个结果以后，由于出现在 x 右边的数字是还没有遇到的，所以，不小于 x 的数字都出现在 x 的左边，那就可以简单地使用 i + 1 - getSum(x) 得到出现在 x 左边、比自己大的数字的个数。

这个公式是显然成立的：对于第 i 个数字，目前已经出现的所有数字一共是 i + 1 个，在这些数字里，不小于 x 的有 getSum(x) 个，所以，大于 x 的有 i + 1 - getSum(x) 个。并且，这些数字要么是 x 本身，要么出现在 x 的左边。

累加所有的 i + 1 - getSum(x)，得到答案。

scanf("%d", &n);
for (int i = 0; i < n; i++) {
    scanf("%d", &x);
    change(x); // 更新树状数组，记下新的数 x
    ans += i + 1 - getSum(x);
    // getSum(x) 是已出现的（在 x 左边的）小于等于 x 的数
    // x 在第 i + 1 位，它和它的左边有 i + 1 个数
    // 所以它左边比它大的数有 i + 1 - getSum(x) 个，有那么多个逆序对，就需要交换那么多次
}
printf("%d", ans);

但是，由于数字范围实在是太大了，我们需要用到离散化的技巧，即将大范围的数字映射到小范围，因为我们只关心数字之间值的大小关系，而不关心具体的数值。

for (int i = 0; i < n; i++) {
    scanf("%d", &x[i]);
    dis[i] = x[i]; // 读入数据，复制一份以便离散化处理
}

对于 C++，可以使用 unique() 函数来去重，首先对 dis数组排序，然后去重，得到去重后的长度 length。在去重后的数组中，用二分查找 x[i] 所在的位置，并用这个位置作为 x[i] 离散化后的值。

sort(dis, dis + n); // 对数据排序
int length = unique(dis, dis + n) - dis; // 利用 unique 去重，使大小与下标对应，并得到去重后的长度
for (int i = 0; i < n; i++) {
    int index = lower_bound(dis, dis + length, x[i]) - dis; // 在去重后的数组中，使用二分查找找到 x[i] 所在位置
    x[i] = index + 1; // 用这个位置作为离散后的值，由于树状数组下标从 1 开始，因此加 1
}

之后的操作与之前类似，遍历 x 数组，change(x[i])，并计算 ans += i + 1 - getSum(x[i])。

最后要注意一下，ans 是 long long 范围的。

以及提一句，unique 和 lower_bound 返回值都是 long long int，直接降级到 int 是一种不好的做法。

完整代码

#include <bits/stdc++.h>

using namespace std;

int n = 0;
const int MAX_N = 500007;
int C[MAX_N] = {0}; // 树状数组
int x[MAX_N] = {0}; // 记录原始数据
int dis[MAX_N] = {0}; // 离散化数据
long long ans = 0;

int lowBit(int x) {
    return x & -x; // return x & (x ^ (x - 1))
}

int getSum(int x) {
    int res = 0;
    while (x != 0) {
        res += C[x];
        x -= lowBit(x);
    }
    return res;
}

void change(int x) {
    while (x <= MAX_N) {
        C[x]++;
        x += lowBit(x);
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &x[i]);
        dis[i] = x[i]; // 读入数据，复制一份以便离散化处理
    }
    sort(dis, dis + n); // 对数据排序
    int length = unique(dis, dis + n) - dis; // 利用 unique 去重，使大小与下标对应，并得到去重后的长度
    for (int i = 0; i < n; i++) {
        int index = lower_bound(dis, dis + length, x[i]) - dis; // 在去重后的数组中，使用二分查找找到 x[i] 所在位置
        x[i] = index + 1; // 用这个位置作为离散后的值，由于树状数组下标从 1 开始，因此加 1
    }
    for (int i = 0; i < n; i++) {
        change(x[i]); // 更新树状数组，记下新的数 x
        ans += i + 1 - getSum(x[i]);
        // getSum(x) 是已出现的（在 x 左边的）小于等于 x 的数
        // x 在第 i + 1 位，它和它的左边有 i + 1 个数
        // 所以它左边比它大的数有 i + 1 - getSum(x) 个，有那么多个逆序对，就需要交换那么多次
    }
    printf("%lld", ans);

    return 0;
}