概要

この問題は、与えられた順列 \(P\) に対して、隣接する要素の入れ替え（スワップ）を最大 \(K\) 回行い、最終的な転倒数を最小化する問題です。

考察

転倒数と隣接スワップの関係

この問題を解くための最大の鍵は、「隣接する 2 要素のスワップ 1 回につき、転倒数はちょうど 1 増えるか 1 減る」という性質です。

• \(P_i > P_{i+1}\) である隣接要素をスワップすると、転倒数は 1 減少します。
• \(P_i < P_{i+1}\) である隣接要素をスワップすると、転倒数は 1 増加します。

目標は転倒数を最小化することなので、可能な限り「転倒数が 1 減るスワップ」を繰り返すべきです。

最適な戦略

転倒数が \(0\) より大きい（＝昇順に並んでいない）とき、必ず \(P_i > P_{i+1}\) となる箇所が存在します。したがって、最大 \(K\) 回のスワップが許されている場合、以下のようになります。

1. 元の転倒数を \(I\) とします。
2. \(K \geq I\) ならば、すべての転倒を解消して転倒数を \(0\) にできます。
3. \(K < I\) ならば、スワップするたびに転倒数を 1 ずつ減らすことで、最小値を \(I - K\) にできます。

結局、この問題は「初期状態の転倒数を効率よく求める」問題に帰着されます。

転倒数の計算方法

転倒数の定義は \(1 \leq i < j \leq N\) かつ \(P_i > P_j\) となる組の数です。 素直に二重ループで数えると \(O(N^2)\) かかり、\(N = 2 \times 10^5\) の制約下では実行時間制限に間に合いません。 そこで、フェニック木（Binary Indexed Tree, BIT）を用いることで、\(O(N \log N)\) で計算することが可能になります。

アルゴリズム

1. BITの準備: 長さ \(N+1\) の BIT を用意します。
2. 転倒数の算出: 順列 \(P\) の要素を先頭から順に見ていき、以下の処理を行います。
   • 現在の要素 \(P_i\) よりも「既に処理された（＝左側にある）」かつ「値が大きい」要素の数を数えます。
   • これは、「既に処理された要素の総数」から「既に処理された \(P_i\) 以下の要素の数」を引くことで求められます。
   • BIT を使って \(P_i\) 以下の要素の数を \(O(\log N)\) で取得し、転倒数に加算します。
   • BIT の \(P_i\) 番目に \(1\) を加算し、出現済みであることを記録します。
3. 答えの出力: max(0, 初期転倒数 - K) を出力します。

計算量

• 時間計算量: \(O(N \log N)\)
  • 順列の各要素に対して、BIT の更新とクエリ（ともに \(O(\log N)\)）を行うためです。
• 空間計算量: \(O(N)\)
  • 入力配列の保持および BIT の管理に \(O(N)\) のメモリを使用します。

実装のポイント

• 高速な入出力: \(N\) が大きいため、Python では sys.stdin.read().split() などを用いて一括で入力を読み込むと高速です。

• 1-indexed: BIT は通常 1-indexed で実装されます。今回のカード番号 \(1 \sim N\) とそのまま対応させることができるため、実装がスムーズになります。

• \(K\) の大きさ: \(K\) は最大 \(10^{18}\) と非常に大きくなる可能性があるため、必ず inv_count - k が負にならないよう max(0, ...) の処理（または if 文による判定）が必要です。

  ソースコード

import sys

def solve():
    # Use sys.stdin.read().split() for fast reading of all input at once.
    # This is more efficient than calling input() multiple times for large N.
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: Number of cards
    # K: Maximum number of adjacent swaps allowed
    n = int(input_data[0])
    k = int(input_data[1])
    
    # P: The current permutation of the cards (1 to N)
    p = list(map(int, input_data[2:]))
    
    # Fenwick Tree (Binary Indexed Tree) to count inversions in O(N log N).
    # The BIT is 1-indexed, which aligns perfectly with card numbers 1 to N.
    bit = [0] * (n + 1)
    inv_count = 0
    
    # Iterate through the permutation and calculate the initial number of inversions.
    # For each element p[i], we count how many elements already processed are greater than it.
    for i, val in enumerate(p):
        # Query: Calculate the count of elements <= val already seen.
        # This loop traverses the BIT structure in O(log N).
        s = 0
        idx = val
        while idx > 0:
            s += bit[idx]
            idx -= idx & -idx
        
        # 'i' is the total number of elements processed before the current element.
        # 's' is the number of those elements that are less than or equal to 'val'.
        # Therefore, 'i - s' is the number of elements processed that are greater than 'val'.
        inv_count += (i - s)
        
        # Update: Add 1 to the BIT at index 'val' to mark it as seen.
        # This loop also runs in O(log N).
        idx = val
        while idx <= n:
            bit[idx] += 1
            idx += idx & -idx
            
    # Each adjacent swap can reduce the inversion count by at most 1.
    # To minimize the inversion count, we perform swaps on pairs (P_i, P_{i+1}) 
    # where P_i > P_{i+1}, which reduces the total inversion count by exactly 1.
    # If the total inversions 'inv_count' is less than or equal to K, we can reach 0.
    # Otherwise, we can reduce the inversion count to 'inv_count - K'.
    result = inv_count - k
    if result < 0:
        result = 0
        
    # Print the minimum possible inversion count.
    print(result)

if __name__ == '__main__':
    solve()

---

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