Overview

This problem asks us to find the minimum number of inversions (degree of disorder) of an array after performing swap operations on adjacent elements exactly \(K\) times.

Let \(I\) be the number of inversions in the initial state. Depending on the relationship between the number of operations \(K\) and \(I\), the minimum number of inversions can be expressed with a simple formula. We can use a Fenwick Tree (Binary Indexed Tree) to calculate the number of inversions quickly.

Observations

1. Relationship Between Adjacent Swaps and Inversions

When we swap two adjacent elements \(P_i\) and \(P_{i+1}\), the total number of inversions changes as follows: - When \(P_i > P_{i+1}\) (descending order): Swapping them decreases the number of inversions by \(1\). - When \(P_i < P_{i+1}\) (ascending order): Swapping them increases the number of inversions by \(1\).

From this, we can derive the following key property:

“With each operation, the number of inversions always changes by \(+1\) or \(-1\) (its parity always flips).”

2. How Much Can We Reduce the Inversions in \(K\) Operations?

Let \(I\) be the number of inversions in the initial state. The minimum number of inversions after \(K\) operations can be analyzed by dividing it into the following two cases:

Case 1: When \(K \le I\)

As long as the number of inversions is \(1\) or more, there always exists an adjacent pair such that \(P_i > P_{i+1}\). By continuously swapping such pairs, we can always perform the “operation that decreases the number of inversions by \(1\)” exactly \(K\) times. Therefore, the minimum number of inversions is \(I - K\).

Case 2: When \(K > I\)

First, by performing \(I\) operations, we can make the array fully sorted (with \(0\) inversions). At this point, the remaining number of operations is \(K - I\).

We must perform further operations from the sorted state. By repeatedly swapping the same adjacent pair (e.g., \(P_1\) and \(P_2\)) back and forth, we can alternate the number of inversions as \(0 \to 1 \to 0 \to 1 \to \dots\). Since the parity of the number of inversions must change with each operation, the final number of inversions is determined by the parity of the remaining operations \(K - I\). - When \(K - I\) is even: The number of inversions can be made \(0\). - When \(K - I\) is odd: The number of inversions can be made \(1\).

Expressed as a formula, this is \((K - I) \bmod 2\).

---

Algorithm

1. Find the initial number of inversions \(I\) The number of inversions can be calculated in \(O(N \log N)\) time by traversing the array from back to front using a Fenwick Tree (BIT). Specifically, for each element \(P_i\), we query the Fenwick Tree to get “the count of numbers smaller than \(P_i\) that have appeared so far.” The sum of these values over all elements gives the total number of inversions \(I\).

2. Output the answer based on conditional branching Compare the calculated number of inversions \(I\) with \(K\).

   • If \(I \ge K\): The answer is \(I - K\).
   • If \(I < K\): The answer is \((K - I) \bmod 2\).

---

Complexity

• Time Complexity: \(O(N \log N)\) We perform element addition and range sum queries on the Fenwick Tree \(N\) times. Since each operation takes \(O(\log N)\) time, the total time complexity is \(O(N \log N)\), which runs sufficiently fast for the constraint \(N \le 2 \times 10^5\).

• Space Complexity: \(O(N)\) Since we store the input array \(P\) and a Fenwick Tree of size \(N + 1\), the space complexity is \(O(N)\).

---

Implementation Details

• Variable Types (Overflow Prevention): The number of operations \(K\) can be up to \(10^{18}\), and the initial number of inversions \(I\) can reach up to \(\frac{N(N-1)}{2} \approx 2 \times 10^{10}\). Since these values exceed the maximum value of a 32-bit signed integer (int), which is about \(2 \times 10^9\), you must use a 64-bit integer type (such as long long in C++).

• Using the AC Library: In C++, using atcoder::fenwick_tree allows you to implement the Fenwick Tree simply and quickly without introducing bugs.

  Source Code

#include <iostream>
#include <vector>
#include <atcoder/fenwicktree>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    long long k;
    if (!(cin >> n >> k)) return 0;

    vector<int> p(n);
    for (int i = 0; i < n; ++i) {
        cin >> p[i];
    }

    atcoder::fenwick_tree<int> fw(n + 1);
    long long inv = 0;
    for (int i = n - 1; i >= 0; --i) {
        inv += fw.sum(0, p[i]);
        fw.add(p[i], 1);
    }

    if (inv >= k) {
        cout << inv - k << "\n";
    } else {
        cout << (k - inv) % 2 << "\n";
    }

    return 0;
}

---

This editorial was generated by gemini-3.5-flash-high.