求排列的逆序数

题目描述

给定 $1,2,\dots,n$ 的一个排列（ $n$ 个互不相同的正整数），统计满足 $i < j$ 且 $a_i > a_j$ 的下标对 $(i,j)$ 的个数，这个数称为排列的逆序数。例如排列 2 6 3 4 5 1 含有 8 个逆序 $(2,1),(6,3),(6,4),(6,5),(6,1),(3,1),(4,1),(5,1)$ ，逆序数为 8。

输入：第一行一个整数 $n$ （ $n \leqslant 100000$ ）；第二行 $n$ 个不同的正整数，以空格隔开，表示该排列（元素取值可达 $10^8$ ）。输出：输出该排列的逆序数。

输入样例：

text

1
26
2 6 3 4 5 1

输出样例：

text

思路

逆序对只依赖元素的相对大小，先把值离散化为排名 $1..n$ ，值域就能开下数组。从左到右扫描，用树状数组（下标为排名）维护"已出现过的值"：设当前排名为 $r$ 、已插入个数为 $k$ ，则新产生的逆序对为 $k - \text{pre}(r)$ （前面比它大的个数），先查询前缀和再单点加 1，累加即答案，总复杂度 $O(n \log n)$ 。

参考代码

Python 版：

python

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#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 01:08
# update_at: 2026-09-30 01:17

import sys


def inversions(perm: list[int]) -> int:
    """求排列（互不相同的数）的逆序数：树状数组统计每个元素前面比它大的个数。

    逆序对只关心相对大小，所以先把值域压成排名 1..n。从左往右扫，
    树状数组的前缀和给出「已经插入的元素里排名不超过当前值」的个数，
    用已插入总数减去它就是新产生的逆序对数。
    """
    n = len(perm)
    rank = {v: i for i, v in enumerate(sorted(perm), 1)}  # 值域 1e8 → 排名 1..n
    bit = [0] * (n + 1)                                  # 下标即排名，1 表示该排名已出现
    ans = 0
    for seen, v in enumerate(perm):
        i = rank[v]
        less = 0                # 已插入元素中排名 ≤ i（即值 ≤ v）的个数
        j = i
        while j:
            less += bit[j]
            j -= j & -j
        ans += seen - less      # 前面 seen 个里比 v 大的都是逆序
        j = i
        while j <= n:
            bit[j] += 1
            j += j & -j
    return ans


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)                          # 排列长度
    perm = [next(data) for _ in range(n)]
    print(inversions(perm))


if __name__ == "__main__":
    solve()

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 06:20
 * update_at: 2026-10-05 06:20
 */

#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long ll;

const int MAXN = 100005;

// a[i]：原序列的值；rk[i]：离散化后的排名（第几小）
int a[MAXN];
int rk[MAXN];

// 树状数组：下标是排名，存"该排名是否已出现过"的计数
int bit[MAXN];
int n;

// 树状数组单点加 1
void bit_add(int i) {
    for (; i <= n; i += i & (-i))
        bit[i] += 1;
}

// 树状数组前缀和：排名 <= i 的已插入元素个数
int bit_sum(int i) {
    int s = 0;
    for (; i > 0; i -= i & (-i))
        s += bit[i];
    return s;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);

    // 离散化：逆序对只依赖相对大小，把值压成排名 1..n
    for (int i = 1; i <= n; ++i)
        rk[i] = a[i];
    sort(rk + 1, rk + n + 1);

    ll ans = 0;      // 完全降序时答案可达 n(n-1)/2，要用 long long
    int seen = 0;    // 已经插入树状数组的元素个数
    for (int i = 1; i <= n; ++i) {
        // 当前值的排名：第一个大于等于 a[i] 的位置（元素互不相同，即第几小）
        int pos = lower_bound(rk + 1, rk + n + 1, a[i]) - rk;
        // 前面 seen 个数中比 a[i] 大的个数 = seen - (排名 <= pos 的个数)
        ans += seen - bit_sum(pos);
        bit_add(pos);
        seen++;
    }

    printf("%lld\n", ans);
    return 0;
}

目录

题目描述

思路

参考代码