概要

与えられた順列に対して、隣り合う要素の交換をちょうど \(K\) 回行った後の、転倒数の最小値を求める問題です。

考察

まず、隣り合う2つの要素を交換する操作が、列の転倒数にどのような影響を与えるかを考えます。 - \(P_i > P_{i+1}\)（逆順）のとき、これらを交換すると転倒数はちょうど \(1\) 減ります。 - \(P_i < P_{i+1}\)（順番通り）のとき、これらを交換すると転倒数はちょうど \(1\) 増えます。

つまり、1回の操作で転倒数を \(1\) 減らすか、\(1\) 増やすかしかできません。 初期状態の転倒数を \(I\) とします。

操作回数 \(K\) と \(I\) によって、以下の2つの場合に分けられます。

1. \(K \leq I\) の場合 逆順になっている隣接要素を交換し続けることで、ちょうど \(K\) 回の操作で転倒数を \(K\) 減らすことができます。これ以上減らす必要はないため、これが最小値となります。したがって、答えは \(I - K\) です。

2. K > I の場合 まず \(I\) 回の操作を行って、転倒数を \(0\)（完全な昇順）にします。このとき、残りの操作回数は \(K - I\) 回です。 転倒数が \(0\) の状態では、どの隣接要素を交換しても転倒数は \(1\) 増えてしまいます。しかし、その直後に同じ要素を再度交換すれば転倒数は \(0\) に戻ります。 つまり、2回の操作で転倒数 \(0\) の状態を維持できます。 したがって、残り回数 \(K - I\) が偶数であれば最終的な転倒数は \(0\)、奇数であれば \(1\) になります。よって、答えは \((K - I) \bmod 2\) です。

アルゴリズム

1. 初期状態の転倒数 \(I\) を求める フェニック木（BIT）を用いて、要素を左から順に見ていき、「すでに見た要素のうち、自分より大きいものの個数」を足し合わせることで \(O(N \log N)\) で求めます。
2. 答えの判定 求めた転倒数 \(I\) と \(K\) を比較します。

• \(K \leq I\) ならば \(I - K\)
• \(K > I\) ならば \((K - I) \bmod 2\) を出力します。

計算量

• 時間計算量: \(O(N \log N)\) BITを用いた転倒数の計算に支配されます。
• 空間計算量: \(O(N)\) BITの構築に配列分のメモリを使用します。

実装のポイント

• \(K\) は最大 \(10^{18}\) と非常に大きいため、32ビット整数（int）ではなく64ビット整数（long long）を用いて計算する必要があります。

• \(K > I\) の場合の剰余計算 (K - inv) % 2 は、K と I の差が負にならない（\(K > I\) のとき正）ため、C++等でも通常の % 演算子で問題なく求められます。

  ソースコード

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

この解説は or-glm5.2-high によって生成されました。