Overview

When arranging books in the order \(1,2,\dots,N\) using only swaps of two adjacent books, find the minimum number of operations required. This is a problem of counting the inversion number of the permutation.

Analysis

The minimum number of adjacent swaps (such as in bubble sort) needed to sort an array in ascending order equals the inversion number of that array.

• An inversion is a pair \((i,j)\) where \(i<j\) but \(A_i>A_j\).
• For example, in \([3,1,2]\), the inversions are \((3,1)\) and \((3,2)\), so the minimum number of operations is 2.

Why the inversion number is the answer: - A single adjacent swap only changes the relative order of two neighboring elements, so the inversion number changes by at most 1. - Since all reversed pairs (inversions) must be resolved to achieve ascending order, at least as many operations as the inversion number are required. - In practice, inversions can be resolved one at a time as in bubble sort, so sorting is always achievable in exactly the inversion number of operations.

Counting inversions naively: - Checking all pairs \((i,j)\) takes \(O(N^2)\), which is too slow for \(N \le 2\times 10^5\) (TLE).

Therefore, we use a data structure (Fenwick tree / BIT) that can quickly count “the number of values seen so far” to compute the inversion number in \(O(N\log N)\).

Algorithm

We scan the array from left to right, letting the current value be \(v=A_i\).

If we can determine how many elements to the left of \(i\) are greater than \(v\), that gives us “the number of inversions created by \(v\).” - Let seen be the number of elements already processed - Among those, the count of elements \(\le v\) is fw.sum(v) (prefix sum from the Fenwick tree) - Therefore, the count of elements greater than \(v\) is seen - fw.sum(v)

Thus, the inversion count inv can be updated as follows: - inv += seen - fw.sum(v) - Then register “one occurrence of value \(v\)” in the Fenwick tree with fw.add(v, 1) - seen += 1

The Fenwick tree (BIT) supports: - add(i, x): add \(x\) to position \(i\) (here, incrementing the occurrence count) - sum(i): compute the total from \(1\) to \(i\) (here, “the number of occurrences of values \(\le i\)”)

Both operations run in \(O(\log N)\).

In this problem, \((A_1,\dots,A_N)\) is a permutation of \(1..N\), so the values can be used directly as Fenwick tree indices (1-indexed).

Complexity

• Time complexity: \(O(N \log N)\) (one sum and one add call per element)
• Space complexity: \(O(N)\) (the Fenwick tree array)

Implementation Notes

• The Fenwick tree is typically implemented with 1-indexing (bit[0] is unused).

• The inversion number can be as large as \(N(N-1)/2\), which for \(N=2\times 10^5\) is approximately \(2\times 10^{10}\), so a 64-bit integer type is needed. Python’s int supports arbitrary precision, so no special handling is required.

• Since the input can be large, reading it all at once with sys.stdin.buffer.read() is faster.

  Source Code

import sys

class Fenwick:
    __slots__ = ("n", "bit")
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def add(self, i, x):
        n = self.n
        bit = self.bit
        while i <= n:
            bit[i] += x
            i += i & -i

    def sum(self, i):
        s = 0
        bit = self.bit
        while i > 0:
            s += bit[i]
            i -= i & -i
        return s

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    n = data[0]
    a = data[1:1+n]

    fw = Fenwick(n)
    inv = 0
    seen = 0
    for v in a:
        inv += seen - fw.sum(v)
        fw.add(v, 1)
        seen += 1

    sys.stdout.write(str(inv))

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.