Overview

This problem asks for the minimum possible number of inversions after swapping adjacent students exactly \(K\) times.

The key point is the property that a single adjacent swap always increases or decreases the number of inversions by exactly \(1\).

Analysis

First, let \(I\) be the number of inversions of the current sequence.

When swapping two adjacent values \(a\) and \(b\):

• If \(a > b\), this adjacent pair is an inversion, so swapping them decreases the number of inversions by \(1\).
• If \(a < b\), this adjacent pair is not an inversion, so swapping them increases the number of inversions by \(1\).

In other words, a single adjacent swap always changes the number of inversions by exactly \(1\).

Case \(K \leq I\)

When the number of inversions is \(I\), we can decrease the number of inversions by \(1\) at a time using adjacent swaps.

Indeed, as long as the sequence is not sorted in ascending order, there exists at least one adjacent inversion, and swapping it will decrease the number of inversions by \(1\).

Therefore, we can use all \(K\) operations to decrease the number of inversions, so the answer is

\[ I - K \]

.

Case \(K > I\)

First, we can make the sequence completely sorted in ascending order using \(I\) adjacent swaps.

At this point, the number of inversions is \(0\).

Let the remaining number of operations be

\[ R = K - I \]

.

If we perform one adjacent swap on an ascending sequence, the number of inversions becomes \(1\).

After that, if we swap the same pair again, it returns to the original state, and the number of inversions becomes \(0\).

Thus, if the remaining number of operations is even, we can repeat the process of swapping and swapping back to end with \(0\) inversions.

On the other hand, if the remaining number of operations is odd, the final number of inversions must be odd. Since the number of inversions cannot be negative, the minimum possible value is \(1\).

Therefore, the answer when \(K > I\) is

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

.

Why Naive Approaches Fail

If we directly simulate the \(K\) adjacent swaps, it will not run in time because \(K\) can be up to \(10^{18}\).

Furthermore, counting the number of inversions naively takes \(O(N^2)\) time because we would need to check all pairs \((i, j)\). Since \(N\) is up to \(2 \times 10^5\), this will also TLE (Time Limit Exceeded).

Thus, we need to calculate the number of inversions \(I\) efficiently.

Algorithm

1. Calculate the number of inversions \(I\) of the initial sequence using a Fenwick Tree (Binary Indexed Tree).
2. If \(K \leq I\), the answer is \(I - K\).
3. If \(K > I\), the answer is \((K - I) \bmod 2\).

Counting Inversions with a Fenwick Tree

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

Among the elements we have already processed, the count of elements greater than \(P_i\) is the number of inversions ending at \(P_i\).

For example, if we have processed \(i\) elements so far and the number of elements less than or equal to \(P_i\) is leq, then the number of elements greater than \(P_i\) is

\[ i - leq \]

.

Summing this up over all elements gives the total number of inversions.

By using a Fenwick Tree, we can perform the following operations in \(O(\log N)\) time each:

• Find the number of elements less than or equal to \(P_i\)
• Insert \(P_i\) into the tree

Complexity

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

Implementation Details

The maximum possible number of inversions is

\[ \frac{N(N-1)}{2} \]

.

When \(N = 2 \times 10^5\), this is approximately \(2 \times 10^{10}\), which exceeds the range of a standard 32-bit signed integer (int).

Therefore, the number of inversions and \(K\) must be stored in 64-bit integer types (e.g., long long in C++).

Also, since the Fenwick Tree can directly use the student IDs from \(1\) to \(N\) as indices, implementing it with 1-based indexing makes it easier to handle.

Source Code

#include <bits/stdc++.h>
using namespace std;

struct Fenwick {
    int n;
    vector<long long> bit;

    Fenwick(int n) : n(n), bit(n + 1, 0) {}

    void add(int idx, long long val) {
        for (; idx <= n; idx += idx & -idx) bit[idx] += val;
    }

    long long sum(int idx) const {
        long long res = 0;
        for (; idx > 0; idx -= idx & -idx) res += bit[idx];
        return res;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    long long K;
    cin >> N >> K;

    vector<int> P(N);
    for (int i = 0; i < N; i++) cin >> P[i];

    if (N == 1) {
        cout << 0 << '\n';
        return 0;
    }

    Fenwick fw(N);
    long long inv = 0;

    for (int i = 0; i < N; i++) {
        long long leq = fw.sum(P[i]);
        inv += i - leq;
        fw.add(P[i], 1);
    }

    long long ans;
    if (K <= inv) {
        ans = inv - K;
    } else {
        ans = (K - inv) % 2;
    }

    cout << ans << '\n';
    return 0;
}

---

This editorial was generated by gpt-5.5-high.