Summary

This problem asks us to find the minimum possible number of inversions of a given permutation after performing adjacent element swaps exactly \(K\) times.

Analysis

First, let’s consider the relationship between the number of inversions and adjacent element swaps. - The number of inversions of a permutation sorted in ascending order is \(0\). - Swapping two adjacent elements reverses their relative order, so the number of inversions always changes by either \(+1\) or \(-1\).

Let \(V\) be the number of inversions in the initial state. Since our goal is to minimize the number of inversions, we generally want to keep choosing swaps that decrease the inversion count (i.e., swaps that subtract \(1\)).

Now, let’s consider the minimum possible number of inversions after \(K\) operations by dividing it into cases.

1. Case where \(K \le V\) Since each operation can decrease the number of inversions by \(1\), we can decrease the number of inversions by \(K\) using \(K\) operations. Since we don’t need to decrease it any further and can stop at exactly \(K\) operations, the final minimum number of inversions is \(V - K\).

2. Case where \(K > V\) First, by performing \(V\) operations, we can reduce the number of inversions to \(0\) (a fully sorted state). However, because we must perform exactly \(K\) operations, we still need to perform the remaining \(K - V\) operations.

Swapping adjacent elements when the inversion count is \(0\) increases the inversion count to \(1\). Swapping those same two elements again to return to the original state brings the inversion count back to \(0\). In other words, starting from an inversion count of \(0\), we can return to an inversion count of \(0\) after \(2\) operations.

Therefore, if the remaining number of operations \(K - V\) is even, we can end with an inversion count of \(0\). On the other hand, if \(K - V\) is odd, we will have one operation left over at the end, so we have no choice but to end with an inversion count of \(1\). Thus, the final minimum number of inversions is \((K - V) \bmod 2\).

Algorithm

1. Find the number of inversions \(V\) in the initial state Calculate the number of inversions in \(O(N \log N)\) time using a BIT (Binary Indexed Tree) or a segment tree. The number of inversions can be found by iterating through the elements from left to right and summing up the count of elements seen so far that are larger than the current element.

2. Output the answer based on conditional branching

   • When \(K \le V\), the answer is \(V - K\)
   • When \(K > V\), the answer is \((K - V) \bmod 2\)

Complexity

• Time Complexity: \(O(N \log N)\) Since we use a BIT to calculate the number of inversions, we perform an \(O(\log N)\) operation for each of the \(N\) elements.
• Space Complexity: \(O(N)\) We use an array to maintain the BIT data structure.

Implementation Points

• In Python, large integers are handled automatically, so there is no issue. However, in languages like C++, since \(K\) can be up to \(10^{18}\), you must use a 64-bit integer type such as long long.

• In the implementation of the BIT, note that the indices are 1-based. It is safe to allocate an array of size around \(N+2\).

  Source Code

import sys

def solve():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    P = [int(x) for x in input().split()]
    
    tree = [0] * (N + 2)
    V = 0
    for i in range(N):
        p = P[i]
        
        s = 0
        idx = p
        while idx > 0:
            s += tree[idx]
            idx -= idx & -idx
            
        V += i - s
        
        idx = p
        while idx <= N:
            tree[idx] += 1
            idx += idx & -idx
            
    if K <= V:
        print(V - K)
    else:
        print((K - V) & 1)

if __name__ == '__main__':
    solve()

This editorial was generated by or-glm5.2-high.