概要

この問題は、与えられた \(1\) から \(N\) までの順列 \(P\) に対して、「隣り合う \(2\) 要素を入れ替える」という操作をちょうど \(K\) 回行ったとき、得られる数列の「転倒数（乱れ度）」の最小値を求める問題です。

考察

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

転倒数とは、数列の中で大小関係が逆転しているペア \((i, j)\) （\(i < j\) かつ \(P_i > P_j\)）の個数です。 隣り合う \(2\) つの要素 \(P_i\) と \(P_{i+1}\) を交換したとき、この \(2\) 要素以外のすべてのペアの前後関係や大小関係は変化しません。変化するのは \(P_i\) と \(P_{i+1}\) の関係だけです。

• \(P_i > P_{i+1}\) のとき：交換すると \(P_i < P_{i+1}\) になるため、転倒数はちょうど \(1\) 減少します。
• \(P_i < P_{i+1}\) のとき：交換すると \(P_i > P_{i+1}\) になるため、転倒数はちょうど \(1\) 増加します。

したがって、どのような隣接交換操作を行っても、転倒数の増減は必ず \(+1\) または \(-1\) になります。

2. 操作回数 \(K\) と初期の転倒数 \(I\) の比較

初期状態の転倒数を \(I\) とします。\(K\) 回の操作で転倒数をどこまで減らせるかは、\(I\) と \(K\) の大小関係によって以下の \(2\) つのケースに分かれます。

ケース 1: \(I \ge K\) の場合

転倒数が \(1\) 以上である限り、必ず \(P_i > P_{i+1}\) となる隣り合う要素が存在します。これらを交換することで、転倒数を確実に \(1\) 減らすことができます。 したがって、毎回の操作で転倒数を \(-1\) し続けることが可能であり、ちょうど \(K\) 回の操作で転倒数を \(I - K\) まで減らすことができます。これが最小値です。

ケース 2: \(I < K\) の場合

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

ソートされた状態（転倒数 \(0\)）から \(1\) 回操作を行うと、転倒数は必ず \(1\) になります。 そこからさらに \(1\) 回操作を行うと、元に戻せば転倒数は \(0\) になり、別の場所を入れ替えれば \(2\) になります。 このように、転倒数の偶奇は操作を \(1\) 回行うたびに必ず反転します。

したがって、残りの操作回数 \(K - I\) の偶奇によって、達成可能な最小値が決まります。 - \(K - I\) が偶数の場合： 同じ \(2\) 要素の入れ替えを往復することで、転倒数を \(0\) にすることができます。 - \(K - I\) が奇数の場合： どうしても最後の \(1\) 回で転倒数を \(1\) 増やす必要があるため、最小値は \(1\) になります。

---

アルゴリズム

この問題を解くための手順は以下の通りです。

1. 初期状態の転倒数 \(I\) を求める
   • 愚直にすべてのペアを比較すると \(O(N^2)\) の計算量がかかり、 \(N \le 2 \times 10^5\) では実行時間制限に間に合いません（TLE）。
   • そのため、フェニック木（Binary Indexed Tree, BIT） を用いて \(O(N \log N)\) で高速に転倒数を求めます。
2. 条件分岐による最小値の決定
   • \(I \ge K\) であれば、答えは \(I - K\) です。
   • \(I < K\) であれば、\((K - I)\) が偶数なら \(0\)、奇数なら \(1\) が答えになります。

フェニック木（BIT）を用いた転倒数の求め方

数列を左から順番に見ていき、現在までに現れた数字をフェニック木に記録していきます。 位置 \(i\) にある要素 \(P_i\) を処理するとき、これまでに現れた数字のうち \(P_i\) より大きいものの個数は、(現在の要素数 i) - (フェニック木における P_i 以下の要素数) で計算できます。これをすべての要素について足し合わせることで、転倒数を求めることができます。

---

計算量

• 時間計算量: \(O(N \log N)\)
  • フェニック木への要素の追加とクエリの取得を \(N\) 回行います。各操作は \(O(\log N)\) で実行できるため、全体の計算量は \(O(N \log N)\) となり、実行時間制限に余裕で間に合います。
• 空間計算量: \(O(N)\)
  • サイズ \(N + 1\) のフェニック木と、入力の数列を保持するための配列が必要となるため、空間計算量は \(O(N)\) です。

---

実装のポイント

• \(K\) の型と値の大きさ: \(K\) は最大で \(10^{18}\) という非常に大きな値になります。Pythonでは自動的に多倍長整数として扱われるためオーバーフローの心配はありませんが、C++などの他言語で実装する場合は、long long 型などの \(64\) ビット整数型を使用する必要があります。

• 1-based indexing: フェニック木は構造上 \(1\) から始まるインデックスを使用するため、数列の要素 \(P_i\)（\(1 \le P_i \le N\)）をそのままインデックスとして使用できます。

  ソースコード

import sys

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    N = int(input_data[0])
    K = int(input_data[1])
    P = [int(x) for x in input_data[2:]]
    
    tree = [0] * (N + 1)
    
    def add(i, x):
        while i <= N:
            tree[i] += x
            i += i & -i
            
    def query(i):
        s = 0
        while i > 0:
            s += tree[i]
            i -= i & -i
        return s

    inv = 0
    for i, x in enumerate(P):
        inv += i - query(x)
        add(x, 1)
        
    if inv >= K:
        print(inv - K)
    else:
        if (K - inv) % 2 == 0:
            print(0)
        else:
            print(1)

if __name__ == '__main__':
    solve()

---

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