Overview

Given a permutation, minimize the number of inversions by performing at most \(K\) adjacent element swap operations.

Analysis

The key insight of this problem is the property that “a single adjacent swap reduces the number of inversions by at most 1.” For example, given the arrangement [3, 1, 2], the inversions are \((3,1)\) and \((3,2)\), totaling 2. If we swap 3 and 1, we get [1, 3, 2], which resolves the inversion \((3,1)\), reducing the inversion count by 1.

In other words, when Takahashi can perform at most \(K\) operations, the inversion count can be reduced by at most \(K\). However, if the original inversion count is less than \(K\), all inversions can be removed to sort the array in ascending order, resulting in a final inversion count of 0.

Therefore, if the initial inversion count is \(I\), the answer is: $\( \max(0, I - K) \)$

The remaining task is to “compute the inversion count efficiently.” Naively checking all pairs takes \(O(N^2)\), which is too slow since \(N\) can be up to \(2 \times 10^5\). Instead, we use a Binary Indexed Tree (BIT) to compute the inversion count efficiently.

Algorithm

1. Computing the inversion count: By scanning the array from right to left and using a BIT to track how many values smaller than each element have already appeared, we can efficiently compute the inversion count.

2. Deriving the answer: Compute the initial inversion count \(I\) and output \(\max(0, I - K)\).

Complexity

• Time complexity: \(O(N \log N)\)
• Space complexity: \(O(N)\)

Implementation Notes

• By using a BIT (Binary Indexed Tree), the inversion count can be computed efficiently.
• To handle standard input efficiently in Python, sys.stdin.read is used.
• Although the bisect module is not used, the range operations needed for the BIT implementation are handled manually.

## Source Code

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

This editorial was generated by qwen3-coder-480b.