洛谷P8613小朋友排队·复盘——浅谈冒泡排序与逆序对

Posted on Edited on In

前言

前两天做了一道蓝桥省赛题，是一道对排序思想和实现细节要求较高的题目，由于初次解题时对问题模型的理解存在偏差，导致我的算法方案迭代了两次，耗费了较多时间。本文旨在对整个求解过程进行技术性复盘，深入剖析错误思路的根源，并最终给出一个高效严谨的正确实现。

题目分析

P8613 [蓝桥杯 2014 省 B] 小朋友排队

理解题目后，我们可以提炼出一个核心流程来简化题目：计算每个小朋友被交换的次数→计算每个小朋友的不高兴程度→求和。

不难发现，每次只能交换位置相邻的两个小朋友实际上就是冒泡排序的操作流程。所以问题也就变成了：对所有小朋友进行冒泡排序，统计出每个小朋友被交换了多少次，并对每个小朋友的不高兴程度进行求和。

接下来我们需要用到一个小结论：对一个序列进行冒泡排序时，总交换次数等于该序列逆序对的数量。结论其实不难理解，对于每一对元素，只有当该对元素为逆序对时，我们才会对其进行交换操作。因此，总交换次数一定严格等于总逆序对数量。

而在本题中，我们需要的不是总交换次数，而是每个元素被交换的次数，这也很好实现，仅需统计包含该元素的逆序对的数量即可。

至于最终的求和部分，只需要对每个小朋友进行一次等差数列求和：f(k) = k * (k+1) / 2，再对所有元素进行求和：Σf(k_i)即可。

算法设计及实现

在明确了计算每个元素的逆序对总数这一核心目标后，我选择使用树状数组+离散化来解决问题，下文的两次算法设计迭代也都将围绕着树状数组来进行。

V1.0 初试

最初的方案基于一个宏观的、但忽略了个体差异的思路，它整合了离散化、树状数组和双向遍历三种核心技术，旨在按身高种类进行逆序对的统计。

设计

  1. 核心数据结构：ans_c 数组

    • 创建一个大小为 size (唯一身高值的数量) 的数组 ans_c，其中 ans_c[idx] 用于存储身高排名为 idx 的所有小朋友的逆序对总数（或其累加值）。

  2. 离散化

    • 动机：
      题目中身高 H_i 的值域可达 10^6，而 n 最多为 10^5。直接使用身高值作为数组下标是不可行的。
    • 实现：
      通过 排序→去重 操作，将所有出现过的身高值映射到一个 [1, size] 的紧凑整数区间。一个原始身高值 H 在排序去重后数组 b 中的位置（下标+1），就是它离散化后的新排名 idx。这个 idx 将作为 ans_c 数组和树状数组的下标。

  3. 树状数组

    • 本质：
      树状数组是一种高效的数据结构，能够在 O(log n) 的时间内，同时完成 单点更新 和 查询前缀和 两种操作。
    • 在本方案中的应用：
      我利用树状数组来动态回答一个核心问题：“在我当前遍历过的集合中，身高排名在某个范围内的有多少人？”
      • update(idx, 1)： 当处理一个身高排名为 idx 的小朋友时，执行此操作，意味着“身高排名为idx的人数+1”。
      • query(idx)： 执行此操作，可以得到“身高排名在 [1, idx] 区间内的人数总和”。

  4. 双向遍历策略

    • 依据：
      一个元素的总逆序对数 k，等于其左侧大于它的元素数，加上其右侧小于它的元素数。这两个部分需要分开计算。

算法执行流程

  • a. 正向遍历 (计算左逆序对):
    • 从左到右遍历原始身高数组 a。
    • 对于每个身高 p，首先查询树状数组 c，计算在 p 左侧、且值大于 p 的元素数量。
    • 将此数量赋值给 ans_c[idx]，其中 idx 是 p 的身高排名。
    • 在树状数组中执行 update(idx, 1)，将当前元素 p 加入“已处理”集合。
  • b. 反向遍历 (计算右逆序对):
    • 清空树状数组 c。
    • 从右到左遍历原始身高数组 a。
    • 对于每个身高 p，查询树状数组 c，计算在 p 右侧、且值小于 p 的元素数量。
    • 将此数量累加到 ans_c[idx] 上。
    • 在树状数组中执行 update(idx, 1)。
  • c. 计算总和:
    • 遍历 ans_c 数组，对每个 k = ans_c[idx]，计算 sum(k) 并求和，得到最终答案。

可行性分析

在编码前，对该方案的复杂度进行预估：

  • 时间复杂度:

    1. 离散化: 核心操作是 std::sort，复杂度为 O(n log n)。
    2. 双向遍历: 包含两次独立的、遍历 n 个元素的循环。在每次循环内部，lower_bound 操作的复杂度为 O(log size)，树状数组的 query 和 update 操作复杂度均为 O(log size)。因此，这两次遍历的总时间复杂度为 O(n log size)。
    3. 最终求和: O(n) 或 O(size)。
    • 由于 size <= n，因此总时间复杂度为 O(n log n)。对于 n = 10^5 的数据规模，10^5 * log(10^5) 约等于 1.7 * 10^6，远在 10^8 的安全线内，不会TLE。

  • 空间复杂度:

    1. a, b 两个 vector 占用 O(n) 空间。
    2. 树状数组 cnt_c 和结果数组 ans_c 均占用 O(size) 空间，最坏情况下 size = n，即 O(n)。
    • 总空间复杂度为 O(n)，对于 n = 10^5，内存占用在可接受范围内。

  • 结论：
    从时间/空间复杂度的角度分析，方案可行。

实现

基于以上思路，我构建了第一版代码。其核心是创建了一个大小为 size 的数组 ans_c，其中 ans_c[idx] 旨在存储身高排名为 idx 的小朋友的总逆序对数。此时我并没有注意到，我的算法设计存在一个严重的漏洞，这也让我的初次提交仅拿到了一个测试点的分数。

初次提交记录

点击展开/折叠 初版代码 
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
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int const maxn = 1e5 + 5;
int n;

vector<int> a, b;

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

ll query(int x, ll arr[]) {
    ll ans_q = 0;
    for (int i = x; i != 0; i -= lowbit(i)) {
        ans_q += arr[i];
    }
    return ans_q;
}

void update(int x, int add, int size, ll arr[]) {
    for (int i = x; i <= size; i += lowbit(i)) {
        arr[i] += add;
    }
}

ll sum(ll x) {
    return (1 + x) * x / 2;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    a.reserve(maxn);
    b.reserve(maxn);
    cin >> n;
    for (int i = 0; i < n; i++) {
        int num;
        cin >> num;
        a.push_back(num);
        b.push_back(num);
    }
    sort(b.begin(), b.end());
    b.erase(unique(b.begin(), b.end()), b.end());
    int size = b.size();
    ll cnt_c[size + 5] = {0}, ans_c[size + 5] = {0};
    int cnt = 0;
    for (int p : a) {
        cnt++;
        int idx = lower_bound(b.begin(), b.end(), p) - b.begin() + 1;
        update(idx, 1, size, cnt_c);
        ans_c[idx] = cnt - query(idx, cnt_c);
    }
    memset(cnt_c, 0, sizeof(cnt_c));
    cnt = 0;
    for (auto it = a.rbegin(); it != a.rend(); ++it) {
        int idx = lower_bound(b.begin(), b.end(), *it) - b.begin() + 1;
        ans_c[idx] += query(idx, cnt_c);
        update(idx, 1, size, cnt_c);
    }
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        ans += sum(ans_c[i]);
    }
    cout << ans << endl;
    return 0;
}

错误分析

该方案在提交后仅获得 10 分，原因在于其数据结构的设计与问题要求不匹配，存在严重的逻辑缺陷。

  • 问题根源：
    当序列中存在多个身高相同的元素时，它们在离散化后会映射到同一个排名 idx。这导致 ans_c[idx] 在计算过程中，会错误地覆盖或累加属于不同原始位置元素的数据。

    例如，对于序列 [H1, H2, H1]，第二个 H1 的计算结果会直接覆盖第一个 H1 的，造成信息丢失。

  • 结论：
    算法的数据统计粒度必须精确到每个独立的个体n，而非每种属性的类别size。

V2.0 改进（AC方案）

为修正上述缺陷，必须调整数据结构，为每个原始元素建立独立的档案。

设计

  1. 创建一个大小为 n 的数组 ans_a，其中 ans_a[i] 用于存储原始序列中第 i 个元素的总交换次数。
  2. 正向遍历 (计算左逆序对):
    • for i from 0 to n-1:
    • 利用树状数组 c 查询在 [0, i-1] 区间内，值大于 a[i] 的元素数量。
    • 结果累加至 ans_a[i]。
    • 将 a[i] 的信息更新到树状数组 c 中。
  3. 反向遍历 (计算右逆序对):
    • 清空树状数组 c。
    • for i from n-1 down to 0:
    • 利用树状数组 c 查询在 [i+1, n-1] 区间内，值小于 a[i] 的元素数量。
    • 结果累加至 ans_a[i]。
    • 将 a[i] 的信息更新到树状数组 c 中。
  4. 计算总和:
    • 遍历 ans_a 数组，对每个 k_i = ans_a[i]，计算 sum(k_i) 并累加，得到最终答案。

可行性分析

  • 时间复杂度:

    • 该方案的核心计算流程与 V1.0 完全一致，依然是“离散化 + 两次 n 循环内嵌 log size 操作”。因此，总时间复杂度仍然是 O(n log n)，性能上依然高效。

  • 空间复杂度:

    • 与 V1.0 的唯一区别在于结果数组。ans_a 的大小为 n，替代了 V1.0 中大小为 size 的 ans_c。在最坏情况下 size=n，两者空间占用相当。
    • 总空间复杂度依然为 O(n)。

  • 结论：
    从时间/空间复杂度的角度分析，方案可行。

实现

该方案通过以数组下标 i 关联原始位置，确保了数据归属的唯一性，且代码实现比 V1.0 更简洁。

最终AC提交记录

点击展开/折叠 最终AC代码 
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
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int const maxn = 1e5 + 5;
int n;

vector<int> a, b;

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

ll query(int x, ll arr[]) {
    ll ans_q = 0;
    for (int i = x; i != 0; i -= lowbit(i)) {
        ans_q += arr[i];
    }
    return ans_q;
}

void update(int x, int add, int size, ll arr[]) {
    for (int i = x; i <= size; i += lowbit(i)) {
        arr[i] += add;
    }
}

ll sum(ll x) {
    return (1 + x) * x / 2;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    a.reserve(maxn);
    b.reserve(maxn);
    cin >> n;
    for (int i = 0; i < n; i++) {
        int num;
        cin >> num;
        a.push_back(num);
        b.push_back(num);
    }
    sort(b.begin(), b.end());
    b.erase(unique(b.begin(), b.end()), b.end());
    int size = b.size();
    ll cnt_c[size + 5] = {0}, ans_a[n + 5] = {0};
    for (int i = 0; i < n; i++) {
        int idx = lower_bound(b.begin(), b.end(), a[i]) - b.begin() + 1;
        update(idx, 1, size, cnt_c);
        ans_a[i] += i + 1 - query(idx, cnt_c);
    }
    memset(cnt_c, 0, sizeof(cnt_c));
    for (int i = n - 1; i >= 0; i--) {
        int idx = lower_bound(b.begin(), b.end(), a[i]) - b.begin() + 1;
        ans_a[i] += query(idx - 1, cnt_c);
        update(idx, 1, size, cnt_c);
    }
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        ans += sum(ans_a[i]);
    }
    cout << ans << endl;
    return 0;
}

  • 实现细节注意：正向与反向遍历的逻辑对称性

    我代码中的两次遍历，在 update 和 query 的顺序与逻辑上，展现了一种精妙的对称性，值得在此详细剖析。

    1. 正向遍历 (计算左逆序对): “先改后查”

      1
      2
      3
      4
      5
      for (int i = 0; i < n; i++) {
          int idx = lower_bound(b.begin(), b.end(), a[i]) - b.begin() + 1;
          update(idx, 1, size, cnt_c);
          ans_a[i] += i + 1 - query(idx, cnt_c);
      }
      • 执行顺序:
        先将当前元素 a[i] 加入树状数组 (update)，再进行查询 (query)。
      • 逻辑解读:
        query(idx, cnt_c) 查询的是包含 a[i] 自身在内的、[0, i] 区间中值小于等于 a[i] 的元素数量。因此，用已处理的总数 i + 1 减去它，就得到了 [0, i] 区间内值大于 a[i] 的数量。由于元素不可能大于自身，该结果精确等价于 a[i] 的左逆序对数。

    2. 反向遍历 (计算右逆序对): “先查后改”

      1
      2
      3
      4
      5
      for (int i = n - 1; i >= 0; i--) {
          int idx = lower_bound(b.begin(), b.end(), a[i]) - b.begin() + 1;
          ans_a[i] += query(idx - 1, cnt_c);
          update(idx, 1, size, cnt_c);
      }
      • 执行顺序:
        先进行查询 (query)，再将当前元素 a[i] 加入树状数组 (update)。
      • 逻辑解读:
        query(idx - 1, cnt_c) 查询的是在 a[i] 被加入之前，树状数组中已有的（即 [i+1, n-1] 区间内的）元素里，排名严格小于 idx（即值严格小于 a[i]）的数量。这直接就是 a[i] 的右逆序对数。

    对比总结：
    正向遍历采用“先改后查”的策略，通过总数减法巧妙地排除了自身的影响；而反向遍历则采用“先查后改”的策略，直接查询所需的结果。两者虽然实现顺序相反，但都最终达成了正确的计算目的，体现了算法实现的灵活性。

P.S. 最后附上我做题时的杂乱草稿（

总结

  1. 问题转化的重要性：本题的核心在于将一个复杂的、带非线性成本的排序问题，成功转化为一个纯粹的、可分步计算的为序列中每个元素统计逆序对的组合计数问题。
  2. 实现与模型的匹配：数据结构的选择与实现，必须在个体粒度上与问题模型保持一致。这是避免在存在重复元素时出现逻辑错误的关键。
  3. 工具的正确使用：树状数组作为一种高效的动态前缀和工具，非常适合在本题的正、反向遍历中，进行动态的范围计数。

希望本次复盘能为解决类似问题提供一个清晰的思路。