概要

隣接する \(2\) 人を交換する操作をちょうど \(K\) 回行った後、転倒数を最小にする問題です。

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

考察

隣り合う \(2\) つの値を交換したとき、転倒数がどう変わるかを考えます。

隣り合う値を \(a, b\) とします。

• \(a > b\) の場合
  この \(2\) つは転倒なので、交換すると転倒が \(1\) つ減ります。
• \(a < b\) の場合
  この \(2\) つは転倒ではないので、交換すると転倒が \(1\) つ増えます。

隣り合っているため、他の要素との転倒関係は変わりません。
したがって、隣接交換 \(1\) 回で転倒数は必ず \(+1\) または \(-1\) だけ変化します。

初期状態の転倒数を \(I\) とします。

\(K \leq I\) の場合

転倒している隣接ペアを交換すれば、転倒数を \(1\) 減らせます。

実際、整列されていない限り、どこかに隣接する転倒ペアが存在します。
そのようなペアを交換し続ければ、最終的に昇順にできます。

昇順にするまでに必要な隣接交換回数はちょうど転倒数 \(I\) 回です。

そのため、\(K \leq I\) なら、\(K\) 回すべてで転倒数を \(1\) ずつ減らせます。

よって答えは

\[ I - K \]

です。

\(K > I\) の場合

まず \(I\) 回の操作で完全に昇順にできます。
この時点で転倒数は \(0\) です。

残りの操作回数を

\[ R = K - I \]

とします。

昇順の状態から隣接交換をすると、転倒数は \(1\) 増えます。
その後、同じ場所をもう一度交換すれば元に戻り、転倒数は \(0\) になります。

つまり、残り操作については

• \(R\) が偶数なら、増やして戻す操作を繰り返せるので転倒数 \(0\)
• \(R\) が奇数なら、最後にどうしても転倒数 \(1\) が残る

となります。

したがって答えは

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

です。

素朴な方法が難しい理由

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

また、各操作でどこを交換するかを探索する必要もありません。
必要なのは初期転倒数 \(I\) だけです。

そのため、転倒数を高速に求めることが重要です。

アルゴリズム

まず、初期順列 \(P\) の転倒数 \(I\) を求めます。

転倒数は、各位置 \(i\) について

\[ j < i \text{ かつ } P_j > P_i \]

となる \(j\) の個数を足し合わせれば求められます。

これを Fenwick Tree、または Binary Indexed Tree を使って \(O(N \log N)\) で計算します。

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

• すでに見た要素数は \(i\)
• すでに見た要素のうち \(P_i\) 以下の個数を Fenwick Tree で求める
• すると、すでに見た要素のうち \(P_i\) より大きい個数は

\[ i - \#\{P_j \leq P_i \mid j < i\} \]

です。

これは、\(P_i\) を右側の要素とする転倒の個数です。

これを全要素について足せば、初期転倒数 \(I\) が得られます。

その後、以下のように答えを出します。

• \(K \leq I\) なら \(I - K\)
• \(K > I\) なら \((K - I) \bmod 2\)

計算量

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

実装のポイント

Fenwick Tree では、値 \(x\) がすでに何回出たかを管理します。

順列なので各値は一度しか出ませんが、出現済みかどうかを \(1\) として加算していけば十分です。

コード中では、左から順に処理しながら

inv += i - s

として転倒数を加算しています。

ここで

• i はこれまでに見た要素数
• s はこれまでに見た要素のうち、現在の値 x 以下の個数

です。

したがって i - s が、現在の値 x より大きい過去の要素数、つまり新しく増える転倒数になります。

また、答えは非常に大きな \(K\) に対しても計算できるよう、実際の操作は行わず、転倒数と偶奇だけで判定します。

ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N = data[0]
    K = data[1]
    P = data[2:]

    bit = [0] * (N + 1)
    inv = 0

    for i, x in enumerate(P):
        s = 0
        idx = x
        while idx > 0:
            s += bit[idx]
            idx -= idx & -idx

        inv += i - s

        idx = x
        while idx <= N:
            bit[idx] += 1
            idx += idx & -idx

    if K <= inv:
        print(inv - K)
    else:
        print((K - inv) & 1)

if __name__ == "__main__":
    main()

---

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