Overview

First, compute the inversion count of the given permutation, then calculate how much the inversion count can be reduced (i.e., the minimum value) by performing at most \(K\) adjacent swaps.

Analysis

Key Observation 1: A single adjacent swap always changes the inversion count by exactly \(1\)

When swapping two adjacent elements (at positions \(i\) and \(i+1\)), only the relative order of those two elements is affected.

• If \(P_i > P_{i+1}\) (an adjacent inversion), swapping them resolves that inversion, and the inversion count decreases by \(1\).
• If \(P_i < P_{i+1}\), swapping them creates a new inversion, and the inversion count increases by \(1\).

In other words, if we choose an operation that reduces the inversion count, it always decreases by exactly 1 per operation.

Key Observation 2: As long as the inversion count is not 0, we can always choose a “reducing” operation

If the inversion count is nonzero, there must exist some \(P_i > P_j\ (i<j)\). In this case, by moving the larger element to the right (swapping adjacent inversions sequentially, like in bubble sort), we can always find an adjacent inversion to swap, reliably reducing the inversion count by 1 each time.

Therefore, if the initial inversion count is \(\mathrm{inv}\), the minimum achievable inversion count is: - When \(K \le \mathrm{inv}\): \(\mathrm{inv}-K\) - When \(K > \mathrm{inv}\): \(0\)

That is, \(\max(\mathrm{inv}-K, 0)\).

Why a Naive Solution Doesn’t Work

• Counting inversions by definition takes \(O(N^2)\), which is too slow for \(N \le 2\times 10^5\).
• Simulating swap operations one by one is also impossible since \(K\) can be up to \(10^{18}\).

All we need is to “compute the initial inversion count efficiently.”

Algorithm

1. Use a Fenwick Tree (Binary Indexed Tree) to compute the initial inversion count \(\mathrm{inv}\) in \(O(N\log N)\).
   • Process \(P\) from left to right, keeping track of the number of elements seen so far as seen.
   • For the current value \(x\), the number of elements seen so far that are \(x\) or less can be obtained from the Fenwick tree as sum(x).
   • Therefore, the number of elements seen so far that are greater than \(x\) is seen - sum(x).
   • This represents the “increase in inversions when placing \(x\) on the right (later),” so we accumulate this to build the inversion count.
2. Output \(\max(\mathrm{inv}-K, 0)\) as the answer.

Example: - For \(P=[3,1,2]\), the inversions are \((3,1)\) and \((3,2)\), so \(\mathrm{inv}=2\). - If \(K=1\), the minimum is \(2-1=1\) (indeed, fixing the adjacent inversion \((3,1)\) gives \([1,3,2]\) with inversion count 1). - If \(K=5\), \(\max(2-5,0)=0\) (it cannot be reduced further).

Complexity

• Time complexity: \(O(N\log N)\) (each element requires \(O(\log N)\) for Fenwick tree update and prefix sum queries)
• Space complexity: \(O(N)\) (for the Fenwick tree array)

Implementation Notes

• The Fenwick tree is 1-indexed, so values \(x(1\ldots N)\) can be used directly as indices.

• Since \(K\) can be as large as \(10^{18}\), instead of iterating through operations, we simply compute \(\mathrm{inv}-K\).

• The maximum inversion count \(\mathrm{inv}\) is \(N(N-1)/2 \approx 2\times 10^{10}\), which can be safely handled by Python’s int.

  Source Code

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, K = data[0], data[1]
    P = data[2:]

    fw = Fenwick(N)
    inv = 0
    seen = 0
    for x in P:
        leq = fw.sum(x)
        inv += seen - leq
        fw.add(x, 1)
        seen += 1

    ans = inv - K
    if ans < 0:
        ans = 0
    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.