Luogu P8613 Review: Bubble Sort, Inversions, and Each Element's Swap Count

Introduction

A couple of days ago, I worked on a Lanqiao Cup provincial-round problem that calls for a solid grasp of sorting and close attention to implementation details. My initial understanding of the model was off, so I went through two versions of the algorithm and spent quite a while on it. This article reviews the entire solution process, examines the roots of the mistaken approach, and arrives at an efficient, rigorous implementation.

Problem Analysis

P8613 [Lanqiao Cup 2014 Provincial Round B] Children Queuing

Once we understand the statement, we can reduce the problem to a simple core process: count how many times each child is swapped → calculate each child’s unhappiness → add the results.

It is easy to see that each move swaps only two adjacent children, which is exactly the operation used by bubble sort. The problem therefore becomes: bubble-sort all the children, count how many times each child is swapped, and sum their individual unhappiness.

We need a small observation: when bubble-sorting a sequence, the total number of swaps equals the number of inversions in the sequence. This is not difficult to understand. For any pair of elements, we swap them only if they form an inversion. Thus, the total swap count must be exactly the total inversion count.

Here, however, we need each element’s swap count, rather than the total swap count. This is straightforward too: count the inversions that involve that element.

For the final sum, apply the arithmetic-series formula to each child, f(k) = k * (k+1) / 2, then sum over all elements: Σf(k_i).

Algorithm Design and Implementation

With counting all inversions involving each element established as the central goal, I chose a Fenwick tree + coordinate compression. Both versions below build on that structure.

V1.0: First Attempt

The initial approach took a broad view but overlooked individual differences. It combined three main techniques—coordinate compression, a Fenwick tree, and traversal in both directions—to count inversions by height category.

Design

Core data structure: the ans_c array
- Create an array ans_c of length size, the number of distinct height values. ans_c[idx] stores the total inversion count, or an accumulated count, for all children whose height rank is idx.
Coordinate compression
- Motivation:
  Heights H_i can be as large as 10^6, while n is at most 10^5. Using the heights directly as array indices is not feasible.
- Implementation:
  Sort → deduplicate to map all heights that appear into the compact integer interval [1, size]. A height H receives a new rank idx equal to its position in the sorted, deduplicated array b, plus 1. This idx indexes both ans_c and the Fenwick tree.
Fenwick tree
- What it does:
  A Fenwick tree efficiently supports both point updates and prefix-sum queries, each in O(log n) time.
- How this approach uses it:
  I use the tree to answer a central question dynamically: “Among the elements I have processed so far, how many have height ranks in a given range?”
  - update(idx, 1): When processing a child of height rank idx, this means “increase the number of people with height rank idx by 1.”
  - query(idx): This returns “the total number of people whose height ranks lie in [1, idx].”
Traversal in both directions
- Reasoning:
  An element’s total inversion count k equals the number of greater elements on its left, plus the number of smaller elements on its right. We calculate the two parts separately.

Algorithm flow

a. Forward traversal (inversions with elements on the left):
- Traverse the original height array a from left to right.
- For each height p, first query the Fenwick tree c to count the elements to the left of p whose values are greater than p.
- Assign this count to ans_c[idx], where idx is the rank of height p.
- Perform update(idx, 1) to add the current element p to the processed set.
b. Reverse traversal (inversions with elements on the right):
- Clear the Fenwick tree c.
- Traverse the original array a from right to left.
- For each height p, query c to count the elements to its right whose values are smaller than p.
- Add this count to ans_c[idx].
- Perform update(idx, 1).
c. Compute the total:
- Traverse ans_c, calculate sum(k) for each k = ans_c[idx], and add the results to obtain the final answer.

Feasibility Analysis

Before coding, I estimated the complexity:

Time complexity:
1. Coordinate compression: The main operation is std::sort, which takes O(n log n).
2. Two traversals: These are two independent loops over n elements. Within each iteration, lower_bound takes O(log size), and the Fenwick tree’s query and update also each take O(log size). The two traversals therefore take O(n log size) overall.
3. Final summation: O(n) or O(size).
- Since size <= n, the overall time complexity is O(n log n). For n = 10^5, 10^5 * log(10^5) is approximately 1.7 * 10^6, well below the safe threshold of 10^8, so it will not TLE.
Space complexity:
1. The two vector containers a and b use O(n) space.
2. The Fenwick tree cnt_c and result array ans_c each use O(size). In the worst case, size = n, giving O(n).
- The overall space complexity is O(n), and memory use is acceptable for n = 10^5.
Conclusion:
From the perspective of time and space complexity, the approach is feasible.

Implementation

I built the first version around this idea. Its central structure is the length-size array ans_c, intended to hold the total inversion count for a child of height rank idx. At the time, I had not noticed a serious flaw in the design. My first submission consequently earned the points for only one test case.

First submission record

Expand/collapse the initial code

#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;
}

What Went Wrong

The submission earned only 10 points because its data structures did not match the problem’s requirements, creating a serious logical flaw.

Root cause:
When several elements have the same height, coordinate compression maps them to the same rank idx. During the calculation, ans_c[idx] therefore incorrectly overwrites or combines data belonging to elements at different original positions.

For example, in [H1, H2, H1], the calculation for the second H1 directly overwrites the result for the first, losing information.
Conclusion:
The counting granularity must correspond to each of the n individual elements, rather than the size distinct attribute categories.

V2.0: Improvement (Accepted Solution)

To correct this flaw, we need to change the data structure so that each original element has its own record.

Design

Create an array ans_a of length n, where ans_a[i] stores the total number of swaps involving the ith element in the original sequence.
Forward traversal (inversions with elements on the left):
- for i from 0 to n-1:
- Query the Fenwick tree c for the number of elements in [0, i-1] whose values are greater than a[i].
- Add the result to ans_a[i].
- Update c with the information for a[i].
Reverse traversal (inversions with elements on the right):
- Clear the Fenwick tree c.
- for i from n-1 down to 0:
- Query c for the number of elements in [i+1, n-1] whose values are smaller than a[i].
- Add the result to ans_a[i].
- Update c with the information for a[i].
Compute the total:
- Traverse ans_a, calculate sum(k_i) for each k_i = ans_a[i], and add the results to obtain the final answer.

Feasibility Analysis

Time complexity:
- The central computation is identical to V1.0: “coordinate compression + two loops of n iterations, each containing log size operations.” The overall time complexity remains O(n log n), so the algorithm remains efficient.
Space complexity:
- The only difference from V1.0 is the result array. The length-n array ans_a replaces the length-size array ans_c. In the worst case, size=n, so their space requirements are comparable.
- The overall space complexity remains O(n).
Conclusion:
From the perspective of time and space complexity, the approach is feasible.

Implementation

By using array index i to identify the original position, this approach gives every piece of data a unique owner. The code is also simpler than V1.0.

Final accepted submission record

Expand/collapse the final accepted code

#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;
}

Implementation detail: symmetry between the forward and reverse traversals

The two traversals in my code show an elegant symmetry in the order and logic of update and query. It is worth examining this in detail.
1. Forward traversal (inversions on the left): “update, then query”
  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);
  }
  - Execution order:
    Add the current element a[i] to the Fenwick tree with update, then perform query.
  - Interpretation:
    query(idx, cnt_c) counts the elements in [0, i] whose values are less than or equal to a[i], including a[i] itself. Subtracting this from the processed count i + 1 gives the number of values greater than a[i] in [0, i]. Since an element cannot be greater than itself, this is exactly the number of inversions involving a[i] and an element on its left.
2. Reverse traversal (inversions on the right): “query, then update”
  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);
  }
  - Execution order:
    Perform query first, then add the current element a[i] to the Fenwick tree with update.
  - Interpretation:
    query(idx - 1, cnt_c) counts the elements already in the tree before a[i] is added—that is, the elements in [i+1, n-1]—whose ranks are strictly less than idx, meaning their values are strictly less than a[i]. This directly gives the number of inversions involving a[i] and an element on its right.
Comparison:
The forward traversal uses “update, then query” and subtracts from the total to remove the current element’s effect. The reverse traversal uses “query, then update” to obtain the desired count directly. Their execution orders are opposite, yet both compute the correct result, illustrating the flexibility of algorithm implementation.

P.S. Finally, here are my messy scratch notes from working on the problem (

Figure legend: The scratch arrays work through coordinate compression and inversion counts on several examples, including repeated heights. The Chinese labels “front” and “back” identify the contributions from the two traversal directions; “expected” marks the intended counts. The final example sums the individual unhappiness values to 26.

Takeaways

The value of a good reduction: The key is turning a complicated sorting problem with nonlinear costs into a clean combinatorial counting problem: count the inversions involving each element in the sequence, in separately computable steps.
Match implementation to the model: Data structures and their implementation must match the model at the individual-element level. This is essential for avoiding logical errors when duplicate elements are present.
Use the right tool: A Fenwick tree is an efficient tool for dynamic prefix sums, making it well suited to the dynamic range counting required by both traversals here.

I hope this review offers a clear approach to similar problems.

Luogu P8613 Review: Bubble Sort, Inversions, and Each Element's Swap Count

Introduction

Problem Analysis