[NOI Online #1 提高组] 冒泡排序

题意

给出一个 $1..n$ 的排列。

操作有两种：

交换当前位置 $x$ 和 $x+1$ 上的两个数
询问当前排列做完 $k$ 轮标准冒泡排序后，还剩多少个逆序对

思路

先看一个可以直接验证想法的朴素解：

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#include <bits/stdc++.h>
using namespace std;

// brute.cpp：直接模拟相邻交换与冒泡排序轮数。
// 只适合小数据，用来帮助理解“每做一轮冒泡排序会发生什么”。

int count_inversion(const vector<int> &a) {
    int n = (int) a.size();
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (a[i] > a[j]) {
                ans++;
            }
        }
    }
    return ans;
}

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

    int n, m;
    cin >> n >> m;

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

    while (m--) {
        int op;
        cin >> op;
        if (op == 1) {
            int x;
            cin >> x;
            --x;
            swap(a[x], a[x + 1]);
        } else {
            int k;
            cin >> k;
            vector<int> b = a;
            int limit = min(k, n);

            for (int round = 0; round < limit; round++) {
                for (int i = 0; i + 1 < n; i++) {
                    if (b[i] > b[i + 1]) {
                        swap(b[i], b[i + 1]);
                    }
                }
            }

            cout << count_inversion(b) << '\n';
        }
    }

    return 0;
}

brute.cpp 每次询问都直接复制当前排列，模拟 $k$ 轮冒泡，然后再暴力数逆序对。

这个做法只能处理很小的数据。

真正关键的是先看懂“一轮冒泡”对逆序对的影响。

对每个值 $x$ ，记：

c[x] = 当前在 x 左边、且比 x 大的数的个数

这就等于值 $x$ 参与的逆序对数量。

一轮冒泡时， $x$ 最多只能向左跨过一个更大的相邻元素，所以它的贡献最多减少 1。

因此做完 $k$ 轮后，值 $x$ 的贡献就是：

$max(c[x] - k, 0)$

总答案自然就是：

$sum(max(c[x] - k, 0))$

于是问题变成两件事：

当前每个 $c[x]$ 是多少
相邻交换后它们如何变化

相邻交换只会影响一对相邻数的大小关系：

如果交换的是顺序对 $a < b$ ，那么 $c[a]$ 增加 1
如果交换的是逆序对 $a > b$ ，那么 $c[b]$ 减少 1

也就是说，每次交换只改动一个 $c[x]$ 。

接着按 $c[x]$ 的大小维护两棵树状数组：

一棵统计每个 $c$ 值出现了多少次
一棵统计这些 $c$ 值的总和

查询 $k$ 时，只统计所有 $c[x] > k$ 的值即可。

代码

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200005;

int n, m;
int p[MAXN];         // p[i] 表示当前位置上的数
int inv_cnt[MAXN];   // inv_cnt[x] 表示当前有多少个比 x 大的数在 x 左边

int bit_val[MAXN];   // 计算初始 inv_cnt 时使用：按值统计出现次数
int bit_num[MAXN];   // 按 inv_cnt 的取值统计有多少个数
long long bit_sum[MAXN]; // 按 inv_cnt 的取值统计 inv_cnt 总和

int lowbit(int x) {
    return x & -x;
}

void add_bit(int bit[], int pos, int val) {
    for (int i = pos; i <= n; i += lowbit(i)) {
        bit[i] += val;
    }
}

int sum_bit(int bit[], int pos) {
    int ret = 0;
    for (int i = pos; i > 0; i -= lowbit(i)) {
        ret += bit[i];
    }
    return ret;
}

void add_bit_sum(int pos, long long val) {
    for (int i = pos; i <= n; i += lowbit(i)) {
        bit_sum[i] += val;
    }
}

long long sum_bit_sum(int pos) {
    long long ret = 0;
    for (int i = pos; i > 0; i -= lowbit(i)) {
        ret += bit_sum[i];
    }
    return ret;
}

// 在“inv_cnt 的分布”上删除旧值，再加入新值。
void modify_inv_cnt(int x, int new_value) {
    int old_value = inv_cnt[x];
    add_bit(bit_num, old_value + 1, -1);
    add_bit_sum(old_value + 1, -old_value);

    inv_cnt[x] = new_value;

    add_bit(bit_num, new_value + 1, 1);
    add_bit_sum(new_value + 1, new_value);
}

long long query_answer(int k) {
    if (k >= n) {
        return 0;
    }

    // 只统计 inv_cnt > k 的那些值。
    int cnt = sum_bit(bit_num, n) - sum_bit(bit_num, k + 1);
    long long s = sum_bit_sum(n) - sum_bit_sum(k + 1);
    return s - 1LL * k * cnt;
}

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

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

    // 预处理每个值 x 的 inv_cnt[x]：
    // 扫描到 p[i] 时，前面一共有 i-1 个数，其中 <= p[i] 的个数能用树状数组求出，
    // 因而“前面比它大的数”就是这两者之差。
    for (int i = 1; i <= n; i++) {
        int x = p[i];
        int not_greater = sum_bit(bit_val, x);
        inv_cnt[x] = (i - 1) - not_greater;
        add_bit(bit_val, x, 1);
    }

    // 建立 inv_cnt 的值域分布。
    for (int x = 1; x <= n; x++) {
        add_bit(bit_num, inv_cnt[x] + 1, 1);
        add_bit_sum(inv_cnt[x] + 1, inv_cnt[x]);
    }

    while (m--) {
        int op;
        cin >> op;

        if (op == 1) {
            int pos;
            cin >> pos;
            int a = p[pos];
            int b = p[pos + 1];

            if (a < b) {
                // 顺序对交换后会变成逆序对，较小值 a 左边多了一个更大的数 b。
                modify_inv_cnt(a, inv_cnt[a] + 1);
            } else {
                // 逆序对交换后会被消掉，较小值 b 左边少了一个更大的数 a。
                modify_inv_cnt(b, inv_cnt[b] - 1);
            }

            swap(p[pos], p[pos + 1]);
        } else {
            int k;
            cin >> k;
            cout << query_answer(k) << '\n';
        }
    }

    return 0;
}

复杂度

初始预处理： $O(n log n)$
每次交换： $O(log n)$
每次询问： $O(log n)$

总复杂度：

$O((n + m) log n)$

空间复杂度：

$O(n)$

总结

这题最难的不是数据结构，而是先把“冒泡若干轮后的逆序对”改写成：

每个值独立贡献
$sum(max(c[x]-k,0))$

一旦得到这个式子，后面的在线交换维护就顺了。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

[NOI Online #1 提高组] 冒泡排序

目录

题意

思路

代码

复杂度

总结

一图流解析