逆序对 - 题目列表

题意

统计满足 $i<j$ 且 $a_i>a_j$ 的下标对数量。

思路

从左到右扫描。处理 value 时，树状数组记录了此前每个排名出现了几次：

prefix 是已经出现且小于等于 value 的数目；
seen - prefix 就是左边严格大于 value 的数目，也是新产生的逆序对数。

原值可能很大，还有重复值，所以先将 sorted(set(values)) 映射到从 1 开始的连续排名。相等元素使用同一排名，并被 prefix 包含，因此不会误算成逆序对。

Python 知识

sorted(set(values)) 同时完成去重和排序。
字典推导式把原值映射为树状数组下标。
iter(map(int, sys.stdin.buffer.read().split())) 适合一次读入大量整数。
i & -i 是树状数组的 lowbit；查询时减去它，修改时加上它。

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23import sys


data = iter(map(int, sys.stdin.buffer.read().split()))
n = next(data)
values = [next(data) for _ in range(n)]
rank = {value: i + 1 for i, value in enumerate(sorted(set(values)))}
tree = [0] * (len(rank) + 1)
answer = 0

for seen, value in enumerate(values):
    index = rank[value]
    prefix = 0
    i = index
    while i:
        prefix += tree[i]
        i -= i & -i
    answer += seen - prefix
    while index < len(tree):
        tree[index] += 1
        index += index & -index

print(answer)

原有 C++ 归并排序版本仍保留在目录中：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 500005;

int n;
int a[MAXN];
int tmp[MAXN];
ll answer;

void merge_sort_count(int l, int r) {
    if (l >= r) {
        return;
    }

    int mid = (l + r) >> 1;
    merge_sort_count(l, mid);
    merge_sort_count(mid + 1, r);

    int i = l;
    int j = mid + 1;
    int k = l;

    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) {
            tmp[k++] = a[i++];
        }
        else {
            // a[i] > a[j] 时，左半边从 i 到 mid 的所有数都和 a[j] 构成逆序对。
            tmp[k++] = a[j++];
            answer += (ll)(mid - i + 1);
        }
    }

    while (i <= mid) {
        tmp[k++] = a[i++];
    }
    while (j <= r) {
        tmp[k++] = a[j++];
    }

    for (int p = l; p <= r; p++) {
        a[p] = tmp[p];
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    answer = 0;
    merge_sort_count(1, n);

    cout << answer << '\n';
    return 0;
}

复杂度

离散化和每次树状数组操作均为 $O(\log n)$ ，总时间 $O(n\log n)$ ，空间 $O(n)$ 。

总结

“扫描到当前位置时，统计左边比它大的数”是逆序对的另一种标准视角。Python 的集合、排序、字典推导式让离散化只需一行核心代码。