Overview

This problem asks for the minimum number of operations to sort a sequence in ascending order using only swaps of adjacent elements. This can be rephrased as a problem of finding the “inversion count (number of inversions)”, which is very well-known in the world of algorithms.

Analysis

Relationship Between Minimum Operations and Inversion Count

It is known that when “sorting by swapping only adjacent elements,” the minimum number of operations required equals the inversion count of the sequence.

The inversion count is the number of pairs \((i, j)\) in a sequence \(A\) such that \(i < j\) and \(A_i > A_j\). For example, for the sequence \((3, 1, 2)\): - \((3, 1)\): \(i=1, j=2\) and \(A_1 > A_2\) - \((3, 2)\): \(i=1, j=3\) and \(A_1 > A_3\)

Two pairs satisfy the condition, so the inversion count is \(2\), and the minimum number of operations needed for sorting is also \(2\).

Why a Naive Approach Won’t Work

The simplest method to compute the inversion count is to check all pairs \((i, j)\) using a double loop. However, this method takes \(O(N^2)\) computation time. Given the constraint \(N \leq 2 \times 10^5\), we get \(N^2 \approx 4 \times 10^{10}\), which far exceeds the typical time limit (2 seconds) and results in TLE.

Therefore, an efficient algorithm of approximately \(O(N \log N)\) is needed.

Algorithm

This problem can be solved efficiently using a data structure called Binary Indexed Tree (BIT / Fenwick Tree).

1. Prepare an empty BIT. This is used to record “the numbers that have appeared so far.”
2. Iterate through the sequence from left to right (let the current element be \(A_i\)).
3. Among the elements that have appeared so far, calculate the number of elements greater than \(A_i\) and add it to the answer.
   • Specifically, this is obtained by subtracting “the number of elements less than or equal to \(A_i\) (computed using the BIT)” from “the current index \(i\) (= the total number of elements that have appeared so far).”
4. Add \(1\) to the \(A_i\)-th position in the BIT to record that “\(A_i\) has appeared.”

By performing this procedure for all \(N\) elements, all inversion pairs are counted without duplication.

Complexity

• Time complexity: \(O(N \log N)\)
  • For each element of the sequence, we perform an update and a query on the BIT. Each operation is \(O(\log N)\), so the overall complexity is \(O(N \log N)\).
• Space complexity: \(O(N)\)
  • Required to maintain a BIT array of size \(N+1\).

Implementation Notes

• BIT indexing: BIT is generally implemented as 1-indexed (starting from index 1). Since the values \(A_i\) in this problem range from \(1\) to \(N\), they can be used directly as BIT indices.

• Inversion count formula: ans += i - query(val)

  • When using 0-indexed i, it represents the total number of elements processed so far.

  • query(val) returns the sum from \(1\) to val, i.e., “the count of numbers less than or equal to val seen so far.”

  • Therefore, the difference gives “the count of numbers greater than val seen so far,” which is the number of inversions involving \(A_i\).

    Source Code

import sys

def solve():
    # 入力の読み込み
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    n = int(input_data[0])
    a = list(map(int, input_data[1:]))
    
    # Binary Indexed Tree (Fenwick Tree) の実装
    # 転倒数（反転数）を求めるために使用する
    bit = [0] * (n + 1)
    
    def update(i, delta):
        while i <= n:
            bit[i] += delta
            i += i & (-i)
            
    def query(i):
        s = 0
        while i > 0:
            s += bit[i]
            i -= i & (-i)
        return s
    
    ans = 0
    for i, val in enumerate(a):
        # これまでに読み込んだ要素の数 i から、
        # 現在の値 val 以下の要素の数を引くことで、
        # val より大きく、かつ val より左にある要素の数（転倒数）を求める
        ans += i - query(val)
        # 現在の値を BIT に追加
        update(val, 1)
        
    # 結果の出力
    print(ans)

if __name__ == "__main__":
    solve()

---

This editorial was generated by gemini-3-flash-preview.