概要

この問題は、隣り合う要素の入れ替え操作をちょうど \(K\) 回行った後の、配列の「転倒数（乱れ度）」の最小値を求める問題です。

初期状態の転倒数を \(I\) としたとき、操作回数 \(K\) と \(I\) の大小関係によって、最小の転倒数は簡単な数式で表すことができます。転倒数を高速に求めるために、Fenwick Tree（Binary Indexed Tree）を使用します。

考察

1. 隣り合う要素の交換と転倒数の関係

隣り合う \(2\) つの要素 \(P_i\) と \(P_{i+1}\) を交換したとき、全体の転倒数は以下のように変化します。 - \(P_i > P_{i+1}\) のとき（逆順）：交換すると転倒数は \(1\) 減少する。 - \(P_i < P_{i+1}\) のとき（昇順）：交換すると転倒数は \(1\) 増加する。

ここから、以下の重要な性質が導かれます。

「操作を \(1\) 回行うごとに、転倒数は必ず \(+1\) または \(-1\) 変化する（偶奇が必ず反転する）」

2. \(K\) 回の操作で転倒数をどこまで減らせるか？

初期状態の転倒数を \(I\) とします。\(K\) 回の操作後の最小転倒数は、以下の \(2\) つのケースに分けて考えることができます。

ケース 1: \(K \le I\) のとき

転倒数が \(1\) 以上ある限り、必ず \(P_i > P_{i+1}\) となる隣り合うペアが存在します。 そのペアを交換し続けることで、常に「転倒数を \(1\) 減らす操作」を \(K\) 回行うことができます。 したがって、最小の転倒数は \(I - K\) となります。

ケース 2: \(K > I\) のとき

まず \(I\) 回の操作を行うことで、配列を完全にソートされた状態（転倒数 \(0\)）にできます。 この時点で、残りの操作回数は \(K - I\) 回です。

ソートされた状態からさらに操作を行う必要がありますが、隣り合う同じペア（例えば \(P_1\) と \(P_2\)）を交互に交換し続ける（往復する）ことで、転倒数を \(0 \to 1 \to 0 \to 1 \to \dots\) と交互に変化させることができます。 操作を \(1\) 回行うごとに転倒数の偶奇は必ず変わるため、残りの回数 \(K - I\) の偶奇によって最終的な転倒数が決まります。 - \(K - I\) が偶数のとき：転倒数は \(0\) にできる。 - \(K - I\) が奇数のとき：転倒数は \(1\) にできる。

これは、式で表すと \((K - I) \bmod 2\) となります。

---

アルゴリズム

1. 初期状態の転倒数 \(I\) を求める 転倒数は、配列を後ろから順に走査しながら Fenwick Tree（BIT）を用いることで、\(O(N \log N)\) で計算できます。 具体的には、各要素 \(P_i\) について「これまでに現れた \(P_i\) 未満の数の個数」を Fenwick Tree で取得し、その値を累積したものが全体の転倒数 \(I\) になります。

2. 条件分岐による答えの出力 求めた転倒数 \(I\) と \(K\) を比較します。

   • \(I \ge K\) のとき：答えは \(I - K\)
   • \(I < K\) のとき：答えは \((K - I) \bmod 2\)

---

計算量

• 時間計算量: \(O(N \log N)\) Fenwick Tree への要素の追加と、区間和の取得を \(N\) 回行います。それぞれの操作は \(O(\log N)\) なので、全体の時間計算量は \(O(N \log N)\) となり、制約の \(N \le 2 \times 10^5\) に対して十分高速に動作します。

• 空間計算量: \(O(N)\) 入力の配列 \(P\) と、サイズ \(N + 1\) の Fenwick Tree を保持するため、空間計算量は \(O(N)\) です。

---

実装のポイント

• 変数の型（オーバーフロー対策）: 操作回数 \(K\) は最大で \(10^{18}\) であり、初期の転倒数 \(I\) も最大で \(\frac{N(N-1)}{2} \approx 2 \times 10^{10}\) に達します。これらは 32 ビット整数型（int）の最大値（約 \(2 \times 10^9\)）を超えるため、C++ では long long 型を使用する必要があります。

• AC Library の活用: C++ では、atcoder::fenwick_tree を使用することで、バグを埋め込むことなくシンプルかつ高速に Fenwick Tree を実装できます。

  ソースコード

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

---

この解説は gemini-3.5-flash-high によって生成されました。