概要

隣接する生徒をちょうど \(K\) 回入れ替えた後、転倒数を最小でいくつにできるかを求める問題です。

ポイントは、隣接交換を \(1\) 回行うと転倒数は必ず \(1\) だけ増えるか減る、という性質です。

考察

まず、現在の列の転倒数を \(I\) とします。

隣り合う \(2\) つの値 \(a, b\) を交換するとき、

• \(a > b\) なら、この隣接ペアは転倒なので、交換すると転倒数は \(1\) 減る
• \(a < b\) なら、この隣接ペアは転倒ではないので、交換すると転倒数は \(1\) 増える

つまり、隣接交換 \(1\) 回で転倒数は必ず \(1\) だけ変化します。

\(K \leq I\) の場合

転倒数が \(I\) あるとき、隣接交換によって転倒数を \(1\) ずつ減らしていくことができます。

実際、列がまだ昇順でないなら、どこかに隣り合う転倒が存在するため、それを交換すれば転倒数を \(1\) 減らせます。

したがって、\(K\) 回すべてを転倒数を減らす操作に使えるので、答えは

\[ I - K \]

です。

\(K > I\) の場合

まず \(I\) 回の隣接交換で列を完全に昇順にできます。

この時点で転倒数は \(0\) です。

残りの操作回数を

\[ R = K - I \]

とします。

昇順の列から隣接交換を \(1\) 回行うと、転倒数は \(1\) になります。

その後、同じ場所をもう一度交換すれば元に戻り、転倒数は \(0\) になります。

つまり、残り操作回数が偶数なら、交換して戻す操作を繰り返すことで転倒数 \(0\) のまま終われます。

一方、残り操作回数が奇数なら、最後に必ず転倒数が奇数になります。転倒数は負にはならないので、最小は \(1\) です。

よって、\(K > I\) の場合の答えは

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

です。

素朴な方法ではなぜ難しいか

実際に \(K\) 回の隣接交換をシミュレーションすると、\(K\) は最大で \(10^{18}\) なので到底間に合いません。

また、転倒数を素朴に数えると、すべての組 \((i, j)\) を調べるため \(O(N^2)\) かかります。\(N\) は最大 \(2 \times 10^5\) なので、これも間に合いません。

そのため、転倒数 \(I\) を高速に求める必要があります。

アルゴリズム

1. 初期列の転倒数 \(I\) を Fenwick Tree（BIT）で求める
2. \(K \leq I\) なら答えは \(I - K\)
3. \(K > I\) なら答えは \((K - I) \bmod 2\)

Fenwick Tree による転倒数の数え方

左から順に \(P_i\) を見ていきます。

すでに見た要素のうち、\(P_i\) より大きいものの個数が、\(P_i\) を右端とする転倒の個数です。

例えば、現在 \(i\) 個の要素を見た後で、\(P_i\) 以下の個数が leq 個なら、\(P_i\) より大きい個数は

\[ i - leq \]

です。

これを全要素について足し合わせると、全体の転倒数になります。

Fenwick Tree を使うことで、

• \(P_i\) 以下の個数を求める
• \(P_i\) を追加する

という操作をそれぞれ \(O(\log N)\) で行えます。

計算量

• 時間計算量: \(O(N \log N)\)
• 空間計算量: \(O(N)\)

実装のポイント

転倒数の最大値は

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

です。

\(N = 2 \times 10^5\) のとき約 \(2 \times 10^{10}\) になるため、int には収まりません。

そのため、転倒数や \(K\) は long long 型で扱う必要があります。

また、Fenwick Tree は出席番号 \(1\) から \(N\) をそのまま添字として使えるため、1-indexed で実装すると扱いやすいです。

ソースコード

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

---

この解説は gpt-5.5-high によって生成されました。