概要

この問題は、隣り合う要素の入れ替えのみを用いて数列を昇順に並べ替える際の最小操作回数を求める問題です。これは、アルゴリズムの世界では非常に有名な「転倒数（反転数）」を求める問題に言い換えられます。

考察

最小操作回数と転倒数の関係

「隣り合う要素のみを入れ替えてソートする」とき、必要な最小の操作回数は、その数列における転倒数と等しくなることが知られています。

転倒数とは、数列 \(A\) において \(i < j\) かつ \(A_i > A_j\) となっているペア \((i, j)\) の個数のことです。 例えば、数列 \((3, 1, 2)\) の場合、

• \((3, 1)\) ： \(i=1, j=2\) で \(A_1 > A_2\)
• \((3, 2)\) ： \(i=1, j=3\) で \(A_1 > A_3\)

の 2 つが条件を満たすため、転倒数は \(2\) となり、ソートに必要な最小操作回数も \(2\) 回となります。

なぜ素朴な方法ではいけないのか

転倒数を求める最も単純な方法は、すべてのペア \((i, j)\) を二重ループで確認することです。しかし、この方法では \(O(N^2)\) の計算時間がかかります。 今回の制約は \(N \leq 2 \times 10^5\) であるため、\(N^2 \approx 4 \times 10^{10}\) となり、一般的な実行時間制限（2秒）を大幅に超えてしまいます（TLE）。

そのため、\(O(N \log N)\) 程度の効率的なアルゴリズムが必要になります。

アルゴリズム

この問題は、Binary Indexed Tree (BIT / Fenwick Tree) というデータ構造を用いることで効率的に解くことができます。

1. 空の BIT を用意します。これは「これまでに出現した数字」を記録するためのものです。
2. 数列を左から順番に見ていきます（現在の要素を \(A_i\) とする）。
3. これまでに出現した要素のうち、\(A_i\) よりも大きい要素の数を計算し、答えに加算します。
   • 具体的には、「現在のインデックス \(i\)（＝これまでに出現した総数）」から「BIT を使って求めた \(A_i\) 以下の要素の数」を引くことで求められます。
4. BIT の \(A_i\) 番目の位置に \(1\) を加算し、「\(A_i\) が出現した」ことを記録します。

この手順を \(N\) 個の要素すべてに対して行うことで、すべての転倒ペアを重複なく数え上げることができます。

計算量

• 時間計算量: \(O(N \log N)\)
  • 数列の各要素について、BIT の更新と取得を行います。それぞれの操作は \(O(\log N)\) であるため、全体で \(O(N \log N)\) となります。
• 空間計算量: \(O(N)\)
  • サイズ \(N+1\) の BIT 配列を保持するために必要です。

実装のポイント

• BIT の添字: BIT は一般的に 1-indexed（1番目から始まる）で実装されます。今回の巻数 \(A_i\) は \(1\) から \(N\) までの値をとるため、そのまま BIT の添字として利用できます。
• 転倒数の計算式: ans += i - query(val)
  • i は 0-indexed で考えている場合、現在までに処理した要素の個数そのものを表します。
  • query(val) は \(1\) から val までの合計、つまり「今までに見た val 以下の数字の個数」を返します。
  • よって、その差分は「今までに見た val より大きい数字の個数」となり、これが \(A_i\) に関する転倒数となります。

ソースコード

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()

---

この解説は gemini-3-flash-preview によって生成されました。