概要

隣り合う2冊の入れ替えだけで本を \(1,2,\dots,N\) の順に並べるとき、必要な最小操作回数を求めます。これは並びの 転倒数（inversion）を数える問題です。

考察

隣接 swap（バブルソートなど）で配列を昇順にするための最小回数は、その配列の 転倒数に一致します。

• 転倒とは、\(i<j\) なのに \(A_i>A_j\) となっている組 \((i,j)\) のこと。
• 例えば \([3,1,2]\) では転倒は \((3,1),(3,2)\) の2つなので、最小操作回数は2回です。

なぜ転倒数が答えになるか：

• 隣接 swap 1回で変化するのは「隣り合う2要素の大小関係」だけで、転倒数は 高々1 しか増減しません。
• 逆順になっているペア（転倒）をすべて解消しないと昇順にならないため、最低でも転倒数回の操作が必要。
• 実際にバブルソートのように転倒を1つずつ解消できるので、転倒数回で必ず並べ替え可能。

素朴に転倒数を数えると：

• 全ての組 \((i,j)\) を調べると \(O(N^2)\) で、\(N \le 2\times 10^5\) では間に合いません（TLE）。

そこで「今までに見た値の個数」を高速に数えるデータ構造（Fenwick木 / BIT）を使って、転倒数を \(O(N\log N)\) で求めます。

アルゴリズム

左から順に配列を見ていき、現在の値を \(v=A_i\) とします。

このとき、\(i\) より左にある要素で \(v\) より大きい個数が分かれば、それが「\(v\) が作る転倒の数」です。

• すでに見た要素数を seen とする
• そのうち \(v\) 以下の個数を fw.sum(v)（Fenwick木の prefix sum）で求める
• すると \(v\) より大きい個数は seen - fw.sum(v)

よって転倒数 inv は次で更新できます：

• inv += seen - fw.sum(v)
• そして fw.add(v, 1) で「値 \(v\) を1個見た」ことをFenwick木に登録
• seen += 1

Fenwick木（BIT）は、

• add(i, x)：位置 \(i\) に \(x\) を加算（ここでは出現回数を足す）
• sum(i)：\(1\) 〜 \(i\) の合計（ここでは「値が \(i\) 以下の出現回数」） をいずれも \(O(\log N)\) で行えます。

この問題では \((A_1,\dots,A_N)\) は \(1..N\) の順列なので、値をそのままFenwick木の添字（1-indexed）として扱えます。

計算量

• 時間計算量: \(O(N \log N)\)（各要素につき sum と add を1回ずつ）
• 空間計算量: \(O(N)\)（Fenwick木の配列）

実装のポイント

• Fenwick木は 1-indexed 実装が基本です（bit[0] は使わない）。
• 転倒数は最大で \(N(N-1)/2\) となり、\(N=2\times 10^5\) なら約 \(2\times 10^{10}\) と大きいので、64bit相当の整数が必要です。Python の int は多倍長なのでそのままでOKです。
• 入力が大きいので sys.stdin.buffer.read() でまとめて読むと高速です。

ソースコード

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

---

この解説は gpt-5.2-high によって生成されました。