【例2.5】求逆序对

题目描述

给定长度为 $n$ 的序列 $a_1, a_2, \dots, a_n$ （ $n \leqslant 10^5$ ， $a_i \leqslant 10^5$ ），求满足 $i < j$ 且 $a_i > a_j$ 的下标对 $(i, j)$ 的个数，即逆序对总数；相等不构成逆序对。第一行为 $n$ ，接下来 $n$ 行每行一个 $a_i$ 。样例 $a = [3, 2, 3, 2]$ 的答案为 $3$ 。

思路

从左往右扫，把已经扫过的元素装进树状数组（按值域维护的权值桶）；扫到 $x$ 时，先查前缀和得到「左边值 $\leqslant x$ 的个数」，再用「已插入元素总数」减去它，就是「左边比 $x$ 大」的个数，累加后把 $x$ 插入桶里。顺序必须是先查后插，否则 $x$ 会和自己配对。整体 $O(n \log V)$ ， $a_i \leqslant 10^5$ 直接开桶即可。

参考代码

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
46
47
48#!/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 04:29
# update_at: 2026-09-30 04:29

import sys


def inversions(values: list[int]) -> int:
    """求逆序对总数：离散化后从左往右扫，用树状数组统计「前面比它大」的个数。

    逆序对只关心相对大小，所以先把每个值换成它在全体不同值中的名次（离散化），
    值域从 1e5 压到至多 n，树状数组的下标才开得下。扫到 x 时，树状数组里装的
    正是它左边的所有数：前缀和给出其中「值 ≤ x」的个数，用已插入个数减掉它，
    剩下的每一个都比 x 大，各自与 x 组成一个逆序对。
    """
    n = len(values)
    rank = {v: i for i, v in enumerate(sorted(set(values)), 1)}  # 值 -> 名次 1..n
    bit = [0] * (n + 1)          # 树状数组：名次 i 已经出现过几次
    total = 0
    for seen, x in enumerate(values):
        i = rank[x]

        prefix = 0               # 已插入元素中名次 ≤ i（即值 ≤ x）的个数
        j = i
        while j:
            prefix += bit[j]
            j -= j & -j
        total += seen - prefix   # 左边比 x 大的那些，各与 x 构成一个逆序对

        j = i                    # 把 x 登记进树状数组
        while j <= n:
            bit[j] += 1
            j += j & -j
    return total


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


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
63
64
65
66
67
68
69
70
71
72/**
 * 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 08:58
 * update_at: 2026-10-05 08:59
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
const int MAXV = 100005;

typedef long long ll;

ll n;
ll a[MAXN];          // 输入序列（值域 ≤ 1e5，存 ll 与答案类型一致）
int bit[MAXV];       // 树状数组：bit[v] 记录值 v 已经出现过几次

// 单点加：名次 i 处 +delta，沿 lowbit 路径向上传播。
void bit_add(int i, int delta) {
    while (i <= MAXV - 1) {
        bit[i] += delta;
        i += i & -i;
    }
}

// 前缀和查询：[1..i] 上的累计次数，沿 lowbit 路径向下收敛。
int bit_sum(int i) {
    int s = 0;
    while (i > 0) {
        s += bit[i];
        i -= i & -i;
    }
    return s;
}

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

// 思路：把「两两比较」改写成「对每个 a_j 统计左边比它大的个数」。
// 用树状数组维护左侧元素的权值桶；查询 (值 ≤ a_j 的个数) 后再插入 a_j。
// 由于 a_i ≤ 1e5，桶直接开 1e5 即可，无需额外离散化。
void solve() {
    ll total = 0;
    for (ll k = 1; k <= n; k++) {
        ll x = a[k];
        // 已经插进桶里的元素总数 = k - 1（按插入顺序计数）。
        // bit_sum(x) 返回桶里「值 ≤ x」的个数。
        // 二者之差就是「左边比 x 大」的逆序对增量。
        ll seen = k - 1;
        ll le = bit_sum((int)x);
        total += seen - le;

        bit_add((int)x, 1);
    }
    cout << total << '\n';
}

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

    read_input();
    solve();

    return 0;
}

【例2.5】求逆序对

目录

题目描述

思路

参考代码