Overview

This problem asks us to minimize the inversion count of a given permutation \(P\) by performing at most \(K\) adjacent element swaps.

Analysis

Relationship Between Inversion Count and Adjacent Swaps

The key insight for solving this problem is the property that “each swap of two adjacent elements changes the inversion count by exactly 1 (either +1 or -1)”.

• Swapping adjacent elements where \(P_i > P_{i+1}\) decreases the inversion count by 1.
• Swapping adjacent elements where \(P_i < P_{i+1}\) increases the inversion count by 1.

Since the goal is to minimize the inversion count, we should repeatedly perform swaps that decrease the inversion count by 1 as much as possible.

Optimal Strategy

When the inversion count is greater than \(0\) (i.e., the sequence is not sorted in ascending order), there always exists a position where \(P_i > P_{i+1}\). Therefore, when at most \(K\) swaps are allowed, the following holds:

1. Let \(I\) be the initial inversion count.
2. If \(K \geq I\), we can eliminate all inversions and reduce the inversion count to \(0\).
3. If \(K < I\), by reducing the inversion count by 1 with each swap, we can achieve a minimum of \(I - K\).

Ultimately, this problem reduces to “efficiently computing the inversion count of the initial state”.

Computing the Inversion Count

The inversion count is defined as the number of pairs where \(1 \leq i < j \leq N\) and \(P_i > P_j\). A naive double loop would take \(O(N^2)\), which is too slow given the constraint \(N = 2 \times 10^5\). By using a Fenwick Tree (Binary Indexed Tree, BIT), we can compute it in \(O(N \log N)\).

Algorithm

1. Prepare the BIT: Initialize a BIT of length \(N+1\).
2. Compute the inversion count: Process the elements of permutation \(P\) from left to right, performing the following operations:
   • Count the number of elements that have “already been processed (i.e., are to the left)” and “have a larger value” than the current element \(P_i\).
   • This can be obtained by subtracting “the number of already processed elements that are \(\leq P_i\)” from “the total number of already processed elements”.
   • Use the BIT to retrieve the count of elements \(\leq P_i\) in \(O(\log N)\), and add the result to the inversion count.
   • Add \(1\) to the \(P_i\)-th position of the BIT to record that this value has been seen.
3. Output the answer: Output max(0, initial inversion count - K).

Complexity

• Time complexity: \(O(N \log N)\)
  • For each element of the permutation, we perform a BIT update and query (both \(O(\log N)\)).
• Space complexity: \(O(N)\)
  • \(O(N)\) memory is used for storing the input array and managing the BIT.

Implementation Notes

• Fast I/O: Since \(N\) can be large, in Python it is faster to read all input at once using sys.stdin.read().split() or similar methods.

• 1-indexed: BITs are typically implemented as 1-indexed. Since the card numbers range from \(1\) to \(N\), they directly correspond to the BIT indices, making implementation straightforward.

• Large \(K\): \(K\) can be as large as \(10^{18}\), so it is essential to ensure that inv_count - k does not become negative by using max(0, ...) (or an if statement check).

  Source Code

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

---

This editorial was generated by gemini-3-flash-thinking.