概要

与えられた順列に対し、隣接する要素の交換操作を最大 \(K\) 回行って、転倒数を最小化する問題。

考察

この問題の鍵となるのは、「1回の隣接スワップで転倒数は最大でも1しか減らない」という性質です。
例えば、並びが [3, 1, 2] の場合、転倒数は \((3,1), (3,2)\) の2つあります。
ここで 3 と 1 を入れ替えると [1, 3, 2] になり、\((3,1)\) の転倒が解消されるので転倒数が1減ります。

つまり、高橋君が最大 \(K\) 回の操作を行えるとき、転倒数は最大で \(K\) だけ減ると考えられます。
ただし、もともとの転倒数が \(K\) より少なかった場合は、すべての転倒を取り除いて昇順にできるので、最終的な転倒数は0になります。

したがって、初期の転倒数を \(I\) とすると、答えは
$\( \max(0, I - K) \)$
となります。

残る課題は、「転倒数を高速に求める」ことです。ナイーブに全ペアを調べると \(O(N^2)\) かかり、\(N\) が最大 \(2 \times 10^5\) なので間に合いません。そこで、Binary Indexed Tree（BIT）を用いて転倒数を高速に求めます。

アルゴリズム

1. 転倒数の計算：
   　配列を右から左に見ながら、各要素より小さい値がすでに何個出現しているかをBITで管理することで、効率的に転倒数を求めます。

2. 答えの導出：
   　初期の転倒数 \(I\) を求め、\(\max(0, I - K)\) を出力します。

計算量

• 時間計算量: \(O(N \log N)\)
• 空間計算量: \(O(N)\)

実装のポイント

• BIT（Binary Indexed Tree）を使うことで、転倒数を高速に求めることができる。
• Pythonの標準入力を高速に処理するため、sys.stdin.readを使っている。
• bisect モジュールは使われていないが、BITの実装に必要な範囲操作は手動で処理されている。

## ソースコード

```python
import sys
from bisect import bisect_left, bisect_right

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    K = int(data[1])
    P = list(map(int, data[2:]))

    # 転倒数を計算する関数 (BITを使用)
    class BIT:
        def __init__(self, size):
            self.size = size
            self.tree = [0] * (size + 1)
        
        def add(self, i, x):
            while i <= self.size:
                self.tree[i] += x
                i += i & -i
        
        def sum(self, i):
            s = 0
            while i > 0:
                s += self.tree[i]
                i -= i & -i
            return s

    def count_inversions(arr):
        bit = BIT(N)
        inv_count = 0
        for i in range(len(arr)-1, -1, -1):
            val = arr[i]
            inv_count += bit.sum(val - 1)
            bit.add(val, 1)
        return inv_count

    initial_inversions = count_inversions(P)

    # 最大でK回の隣接スワップで減らせる最大転倒数 = min(K, initial_inversions)
    # なぜなら、1回の隣接スワップで転倒数は最大1減るため
    max_decrease = min(K, initial_inversions)
    result = initial_inversions - max_decrease
    print(result)

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。