Overview

This problem asks us to minimize the number of inversions after performing the operation of swapping two adjacent elements exactly \(K\) times.

The key point is the property that swapping two adjacent elements always changes the number of inversions by exactly \(+1\) or \(-1\).

Observation

Let’s consider how the number of inversions changes when we swap two adjacent values.

Let \(a\) and \(b\) be the adjacent values.

• If \(a > b\):
  These two form an inversion, so swapping them decreases the number of inversions by \(1\).
• If \(a < b\):
  These two do not form an inversion, so swapping them increases the number of inversions by \(1\).

Since they are adjacent, their relationship with other elements does not change.
Therefore, a single swap of adjacent elements always changes the number of inversions by exactly \(+1\) or \(-1\).

Let \(I\) be the initial number of inversions.

Case \(K \leq I\)

By swapping an adjacent pair that forms an inversion, we can decrease the number of inversions by \(1\).

In fact, as long as the sequence is not sorted, there is always at least one adjacent pair that forms an inversion.
By repeatedly swapping such pairs, we can eventually sort the sequence in ascending order.

The number of adjacent swaps required to sort the sequence in ascending order is exactly the number of inversions \(I\).

Therefore, if \(K \leq I\), we can decrease the number of inversions by \(1\) in each of the \(K\) operations.

Thus, the answer is

\[ I - K \]

Case \(K > I\)

First, we can completely sort the sequence in ascending order using \(I\) operations.
At this point, the number of inversions is \(0\).

Let the remaining number of operations be

\[ R = K - I \]

If we swap adjacent elements from a sorted state, the number of inversions increases by \(1\).
If we swap the same pair again, it returns to the sorted state, and the number of inversions becomes \(0\).

In other words, for the remaining operations:

• If \(R\) is even, we can repeat the process of increasing and then decreasing, resulting in \(0\) inversions.
• If \(R\) is odd, we are forced to end up with exactly \(1\) inversion.

Therefore, the answer is

\[ (K - I) \bmod 2 \]

Why a Naive Approach is Impractical

If we actually simulate the process \(K\) times, it will not run within the time limit because \(K\) can be up to \(10^{18}\).

Furthermore, we do not need to search for which elements to swap in each operation.
All we need is the initial number of inversions \(I\).

Therefore, the key is to calculate the number of inversions efficiently.

Algorithm

First, we find the number of inversions \(I\) of the initial permutation \(P\).

The number of inversions can be found by summing up, for each position \(i\), the number of indices \(j\) such that

\[ j < i \text{ and } P_j > P_i \]

We can calculate this in \(O(N \log N)\) using a Fenwick Tree (Binary Indexed Tree).

We process \(P_i\) from left to right.

• The number of elements processed so far is \(i\).
• We find the number of already processed elements that are less than or equal to \(P_i\) using the Fenwick Tree.
• Then, the number of already processed elements that are greater than \(P_i\) is:

\[ i - \#\{P_j \leq P_i \mid j < i\} \]

This represents the number of inversions where \(P_i\) is the right element of the pair.

By summing this over all elements, we obtain the initial number of inversions \(I\).

After that, we output the answer as follows:

• If \(K \leq I\), the answer is \(I - K\).
• If \(K > I\), the answer is \((K - I) \bmod 2\).

Complexity

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

Implementation Points

In the Fenwick Tree, we keep track of how many times each value \(x\) has appeared.

Since \(P\) is a permutation, each value appears at most once, so it is sufficient to add \(1\) to represent that the value has appeared.

In the code, while processing from left to right, we add to the inversion count as follows:

inv += i - s

Here,

• i is the number of elements processed so far.
• s is the number of elements processed so far that are less than or equal to the current value x.

Therefore, i - s is the number of previously processed elements that are greater than the current value x, which corresponds to the number of newly formed inversions.

In addition, to handle extremely large values of \(K\), we do not perform the actual operations. Instead, we determine the answer using only the number of inversions and parity.

Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N = data[0]
    K = data[1]
    P = data[2:]

    bit = [0] * (N + 1)
    inv = 0

    for i, x in enumerate(P):
        s = 0
        idx = x
        while idx > 0:
            s += bit[idx]
            idx -= idx & -idx

        inv += i - s

        idx = x
        while idx <= N:
            bit[idx] += 1
            idx += idx & -idx

    if K <= inv:
        print(inv - K)
    else:
        print((K - inv) & 1)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.