Overview

This problem asks us to find the minimum possible number of inversions (the number of pairs \((i, j)\) such that \(i < j\) and \(P_i > P_j\)) that can be achieved after swapping adjacent elements exactly \(K\) times on a permutation.

Analysis

First, an important fact is that swapping two adjacent elements always changes the number of inversions by exactly \(+1\) or \(-1\).

• If \(P_i > P_{i+1}\) for the two swapped elements, this inverted pair is resolved, so the number of inversions decreases by \(1\).
• Conversely, if \(P_i < P_{i+1}\), a new inverted pair is created, so the number of inversions increases by \(1\).

Since the relationship of the swapped elements with all other elements remains unchanged, the change in the number of inversions per operation is always \(\pm 1\).

Let \(T\) be the number of inversions in the initial state. We need to find the minimum possible number of inversions after performing the operation “exactly \(K\) times”.

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

If we always choose an operation that decreases the number of inversions (i.e., swapping an adjacent pair in reverse order), we can reduce the number of inversions to \(T - K\) in \(K\) operations. Since \(K \le T\), such a decreasing operation is guaranteed to exist at each step, so the minimum value is \(T - K\).

Case 2: When \(K > T\)

The minimum possible number of inversions is \(0\) (when the permutation is fully sorted). We can reduce the number of inversions to \(0\) in \(T\) operations, but we still have \(r = K - T\) operations remaining.

The key point is that we must perform the remaining operations exactly \(r\) times. From \(0\) inversions, we can only increase the count, but swapping the same pair twice returns the permutation to its original state. Therefore, we focus on the parity of the remaining operations:

• If \(r\) is even, we can maintain \(0\) inversions by repeatedly “swapping and swapping back” a chosen adjacent pair \(\rightarrow\) the answer is \(0\).
• If \(r\) is odd, we are left with exactly one extra swap at the end, so we cannot achieve \(0\) inversions \(\rightarrow\) the minimum is \(1\).

Thus, the key property is that the number of inversions always changes by \(\pm 1\) (meaning the parity of the number of inversions flips with each operation).

Drawback of the Naive Approach

Counting the initial inversions \(T\) using nested loops takes \(O(N^2)\) time, which will TLE for \(N \le 2\times10^5\). Furthermore, since \(K \le 10^{18}\) is extremely large, simulating the operations one by one is impossible. Based on the analysis above, we leverage the fact that the answer is determined solely by the relationship between \(T\) and \(K\) without actually simulating the operations.

Algorithm

1. Calculate the number of inversions \(T\): Using a BIT (Binary Indexed Tree / Fenwick Tree), we iterate through the elements from left to right, adding them to the BIT and summing up “the number of already added elements that are strictly greater than the current element”. This allows us to find the number of inversions in \(O(N \log N)\) time.
2. Case Analysis:
   • If \(K \le T\), the answer is \(T - K\).
   • If \(K > T\), let \(r = K - T\). If \(r\) is even, the answer is \(0\); if \(r\) is odd, the answer is \(1\).

Complexity

• Time Complexity: \(O(N \log N)\) (dominated by the inversion counting using BIT)
• Space Complexity: \(O(N)\)

Key Implementation Points

• Since \(K\) and the number of inversions \(T\) can be as large as \(\frac{N(N-1)}{2} \approx 2\times10^{10}\) and \(K \le 10^{18}\), they must be stored in 64-bit integers (long long).

• To find “the number of elements greater than the current value” using a BIT, we subtract “the number of elements less than or equal to the current value sum(v)” from the total number of elements already processed \(i\) (i.e., i - sum(v)). Since the values are from \(1\) to \(N\), they can be used directly as indices for the BIT.

• The conditional logic is very simple, only requiring a comparison between \(T\) and \(K\) and a parity check on \(r = K - T\).

  Source Code

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

int main(){
    int N;
    long long K;
    scanf("%d %lld", &N, &K);
    vector<int> P(N);
    for(int i=0;i<N;i++) scanf("%d", &P[i]);
    
    // inversion count using BIT
    vector<long long> bit(N+1, 0);
    auto add=[&](int i){ for(; i<=N; i+= i&(-i)) bit[i]+=1; };
    auto sum=[&](int i){ long long s=0; for(; i>0; i-= i&(-i)) s+=bit[i]; return s; };
    
    long long T=0;
    for(int i=0;i<N;i++){
        int v=P[i];
        // count of already added values greater than v
        // already added = i elements, those <= v = sum(v)
        long long less_eq = sum(v);
        T += (long long)i - less_eq;
        add(v);
    }
    
    long long ans;
    if(K <= T){
        ans = T - K;
    } else {
        long long r = K - T;
        ans = (r % 2 == 0) ? 0 : 1;
    }
    printf("%lld\n", ans);
    return 0;
}

---

This editorial was generated by claude4.8opus-high.