Summary

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

Analysis

First, let’s consider how swapping two adjacent elements affects the number of inversions of the sequence. - When \(P_i > P_{i+1}\) (out of order), swapping them decreases the number of inversions by exactly \(1\). - When \(P_i < P_{i+1}\) (in order), swapping them increases the number of inversions by exactly \(1\).

In other words, a single operation can only decrease the number of inversions by \(1\) or increase it by \(1\). Let \(I\) be the number of inversions in the initial state.

Depending on the number of operations \(K\) and \(I\), we can divide the problem into the following two cases:

1. Case \(K \leq I\) By repeatedly swapping adjacent elements that are out of order, we can decrease the number of inversions by \(K\) in exactly \(K\) operations. Since we cannot decrease it any further, this is the minimum possible value. Therefore, the answer is \(I - K\).

2. Case \(K > I\) First, we perform \(I\) operations to reduce the number of inversions to \(0\) (making the permutation fully sorted in ascending order). At this point, the remaining number of operations is \(K - I\). When the number of inversions is \(0\), swapping any adjacent elements will increase the number of inversions by \(1\). However, if we immediately swap the same elements again, the number of inversions returns to \(0\). In other words, we can maintain \(0\) inversions using every \(2\) operations. Therefore, if the remaining number of operations \(K - I\) is even, the final number of inversions will be \(0\); if it is odd, the final number of inversions will be \(1\). Thus, the answer is \((K - I) \bmod 2\).

Algorithm

1. Find the number of inversions \(I\) in the initial state Using a Fenwick tree (Binary Indexed Tree / BIT), we iterate through the elements from left to right and sum up the “number of already processed elements that are larger than the current element”. This can be computed in \(O(N \log N)\).
2. Determine the answer Compare the calculated number of inversions \(I\) with \(K\).

• If \(K \leq I\), output \(I - K\).
• If \(K > I\), output \((K - I) \bmod 2\).

Complexity

• Time Complexity: \(O(N \log N)\) This is dominated by the inversion count calculation using the BIT.
• Space Complexity: \(O(N)\) We use memory proportional to the array size to construct the BIT.

Implementation Points

• Since \(K\) can be as large as \(10^{18}\), you must use 64-bit integers (long long in C++) instead of 32-bit integers (int) for the calculations.

• For the modulo calculation (K - inv) % 2 when \(K > I\), since the difference between \(K\) and \(I\) is non-negative (positive when \(K > I\)), it can be safely computed using the standard % operator in languages like C++.

  Source Code

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

using namespace std;
using namespace atcoder;

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];
    }

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

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

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

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