Overview

This problem asks you to compute the inversion count of a permutation and, using the fact that a single adjacent swap can decrease the inversion count by at most 1, find the minimum inversion count achievable after at most \(K\) operations.

Analysis

Key Insight: Relationship Between Adjacent Swaps and Inversion Count

Consider the operation of swapping two adjacent elements \(P_i\) and \(P_{i+1}\). The relative order with respect to all other elements remains unchanged. The only relationship that changes is the one between \(P_i\) and \(P_{i+1}\).

• If \(P_i > P_{i+1}\) (an inversion exists), swapping them decreases the inversion count by exactly 1
• If \(P_i < P_{i+1}\) (no inversion), swapping them increases the inversion count by exactly 1

In other words, by choosing swaps wisely, each operation can reliably decrease the inversion count by 1.

Concrete Example

For \(P = [3, 1, 2]\), the inversions are \((3,1)\) and \((3,2)\), giving an inversion count of 2.

• 1st operation: Swap \(P_1=3\) and \(P_2=1\) → \([1, 3, 2]\) (inversion count 1)
• 2nd operation: Swap \(P_2=3\) and \(P_3=2\) → \([1, 2, 3]\) (inversion count 0)

If \(K=1\), the answer is \(1\). If \(K=2\), the answer is \(0\).

Conclusion

Let \(I\) be the current inversion count. The minimum inversion count achievable after at most \(K\) operations is:

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

Since the inversion count cannot go below 0, we compare with 0 using \(\max\).

Why a Naive Inversion Count Computation Doesn’t Work

Computing the inversion count by checking all pairs according to the definition takes \(O(N^2)\) time. For \(N \leq 2 \times 10^5\), this requires up to \(4 \times 10^{10}\) comparisons, resulting in TLE. Instead, we use a BIT (Binary Indexed Tree / Fenwick Tree) to compute it in \(O(N \log N)\).

Algorithm

1. Computing the inversion count using a BIT:

   • Scan the array from left to right, processing each element \(P_i\)
   • Before inserting \(P_i\), find “the number of already inserted elements that are greater than \(P_i\).” This is obtained by subtracting “the count of elements ≤ \(P_i\)” from \(i\) (the number of elements already inserted)
   • Use query(P[i]) on the BIT to get the number of inserted elements ≤ \(P_i\), and add \(i - \text{query}(P_i)\) to the inversion count
   • Then use update(P[i]) to add \(P_i\) to the BIT

2. Computing the answer:

   • Output \(\text{result} = \max(0, \, I - K)\)

Complexity

• Time complexity: \(O(N \log N)\) (the BIT-based inversion count computation is the bottleneck)
• Space complexity: \(O(N)\) (for the BIT array)

Implementation Notes

• Since \(K\) can be as large as \(10^{18}\), you need to use a language or type that supports 64-bit integers (Python naturally handles this with arbitrary-precision integers)

• The inversion count itself can be as large as \(\frac{N(N-1)}{2} \approx 2 \times 10^{10}\), so be careful about 32-bit integer overflow (e.g., in C++)

• It is standard practice to manage BIT indices as 1-indexed

  Source Code

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

---

This editorial was generated by claude4.6opus-thinking.