概要

順列の転倒数を求め、隣接スワップ1回で転倒数が最大1減ることを利用して、最大 \(K\) 回の操作後に達成できる転倒数の最小値を求める問題です。

考察

重要な気づき：隣接スワップと転倒数の関係

隣り合う2つの要素 \(P_i\) と \(P_{i+1}\) を入れ替える操作を考えます。このとき、他のすべての要素との大小関係は変わりません。変化するのは \(P_i\) と \(P_{i+1}\) の間の関係だけです。

• もし \(P_i > P_{i+1}\)（転倒している）なら、スワップすると転倒数は ちょうど1減る
• もし \(P_i < P_{i+1}\)（転倒していない）なら、スワップすると転倒数は ちょうど1増える

つまり、賢くスワップを選べば、1回の操作で転倒数を確実に1減らせます。

具体例

\(P = [3, 1, 2]\) の場合、転倒数は \((3,1), (3,2)\) の2つです。

• 1回目の操作：\(P_1=3\) と \(P_2=1\) をスワップ → \([1, 3, 2]\)（転倒数1）
• 2回目の操作：\(P_2=3\) と \(P_3=2\) をスワップ → \([1, 2, 3]\)（転倒数0）

\(K=1\) なら答えは \(1\)、\(K=2\) なら答えは \(0\) です。

結論

現在の転倒数を \(I\) とすると、最大 \(K\) 回の操作後に達成できる転倒数の最小値は：

\[\max(0, \, I - K)\]

転倒数は0未満にはなれないため、\(\max\) で0と比較します。

素朴な転倒数計算ではなぜダメか

転倒数を定義通り全ペアを調べて計算すると \(O(N^2)\) となり、\(N \leq 2 \times 10^5\) では最大 \(4 \times 10^{10}\) 回の比較が必要で TLE になります。そこで BIT（Binary Indexed Tree / Fenwick Tree） を使って \(O(N \log N)\) で計算します。

アルゴリズム

1. BIT を用いた転倒数の計算：

   • 配列を左から順に走査し、各要素 \(P_i\) を処理する
   • \(P_i\) を挿入する前に、「既に挿入された要素のうち \(P_i\) より大きいものの個数」を求める。これは \(i\)（既に挿入した個数）から「\(P_i\) 以下の個数」を引けば得られる
   • BIT の query(P[i]) で \(P_i\) 以下の挿入済み要素数を取得し、\(i - \text{query}(P_i)\) を転倒数に加算
   • その後 update(P[i]) で BIT に \(P_i\) を追加

2. 答えの計算：

   • \(\text{result} = \max(0, \, I - K)\) を出力する

計算量

• 時間計算量: \(O(N \log N)\)（BIT を用いた転倒数の計算がボトルネック）
• 空間計算量: \(O(N)\)（BIT 用の配列）

実装のポイント

• \(K\) は最大 \(10^{18}\) と非常に大きいため、64ビット整数を扱える言語・型を使う必要がある（Python は多倍長整数なので自然に対応）

• 転倒数自体も最大 \(\frac{N(N-1)}{2} \approx 2 \times 10^{10}\) になりうるため、32ビット整数ではオーバーフローする点に注意（C++ などの場合）

• BIT のインデックスは1-indexed で管理するのが定石

  ソースコード

import sys
from collections import defaultdict

def solve():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    K = int(input_data[1])
    P = [int(input_data[i + 2]) for i in range(N)]
    
    # Calculate inversion count using BIT (Fenwick Tree)
    bit = [0] * (N + 1)
    
    def update(i):
        while i <= N:
            bit[i] += 1
            i += i & (-i)
    
    def query(i):
        s = 0
        while i > 0:
            s += bit[i]
            i -= i & (-i)
        return s
    
    inversions = 0
    for i in range(N):
        # Count elements already inserted that are greater than P[i]
        inversions += i - query(P[i])
        update(P[i])
    
    # Each adjacent swap can reduce the inversion count by at most 1
    result = max(0, inversions - K)
    print(result)

solve()

---

この解説は claude4.6opus-thinking によって生成されました。