概要

与えられた順列の転倒数をまず求め、隣接スワップを最大 \(K\) 回行うことで転倒数をどこまで減らせるか（最小値）を計算します。

考察

重要な気づき 1：隣接スワップ 1 回で転倒数は必ず \(1\) だけ変わる

隣接する 2 枚（位置 \(i,i+1\)）を入れ替えると、影響を受けるのはその 2 枚の大小関係だけです。

• もし \(P_i > P_{i+1}\)（隣接転倒）なら、それを入れ替えるとその転倒が解消され、転倒数は \(-1\) されます。
• もし \(P_i < P_{i+1}\) なら、入れ替えると新たに転倒が 1 つ生まれ、転倒数は \(+1\) されます。

つまり、「転倒数を減らす操作」を選べば 1 回あたり必ず 1 減ることが分かります。

重要な気づき 2：転倒数が 0 になるまで、常に「減らす操作」を選べる

転倒数が 0 でないなら、どこかに \(P_i > P_j\ (i<j)\) が存在します。このとき、その「大きい方」を右へ動かしていく（バブルソートのように隣接転倒を逐次交換する）ことで、毎回「隣接転倒」を見つけて交換でき、転倒数を 1 ずつ確実に減らせます。

したがって、初期転倒数を \(\mathrm{inv}\) とすると、最小到達可能な転倒数は - \(K \le \mathrm{inv}\) のとき：\(\mathrm{inv}-K\) - \(K > \mathrm{inv}\) のとき：\(0\) つまり \(\max(\mathrm{inv}-K, 0)\) です。

素朴解がダメな理由

• 転倒数を定義通りに数えると \(O(N^2)\) で、\(N \le 2\times 10^5\) では間に合いません。
• スワップ操作を逐次シミュレーションするのも、\(K\) が最大 \(10^{18}\) なので不可能です。

必要なのは「初期転倒数を高速に求める」ことだけになります。

アルゴリズム

1. Fenwick 木（Binary Indexed Tree） を用いて初期転倒数 \(\mathrm{inv}\) を \(O(N\log N)\) で求めます。
   • 左から順に \(P\) を見ていき、これまでに見た要素数を seen とする。
   • 現在の値を \(x\) とすると、これまでに見た要素のうち \(x\) 以下の個数 は Fenwick 木で sum(x) として得られる。
   • よって、これまでに見た要素のうち \(x\) より大きい個数は seen - sum(x)。
   • これは「\(x\) を右側（後）に置いたときの転倒の増分」なので、それを累積して転倒数を作る。
2. 答えは \(\max(\mathrm{inv}-K, 0)\) を出力します。

例： - \(P=[3,1,2]\) の転倒は \((3,1),(3,2)\) の 2 個なので \(\mathrm{inv}=2\)。 - \(K=1\) なら最小は \(2-1=1\)（実際、隣接転倒 \((3,1)\) を直すと \([1,3,2]\) で転倒数 1）。 - \(K=5\) なら \(\max(2-5,0)=0\)（これ以上下げられない）。

計算量

• 時間計算量: \(O(N\log N)\)（Fenwick 木での加算・区間和が各要素につき \(O(\log N)\)）
• 空間計算量: \(O(N)\)（Fenwick 木の配列）

実装のポイント

• Fenwick 木は 1-indexed なので、値 \(x(1\ldots N)\) をそのまま添字として使えます。

• \(K\) が \(10^{18}\) と大きいので、操作回数を回すのではなく \(\mathrm{inv}-K\) を計算するだけにします。

• 転倒数 \(\mathrm{inv}\) の最大は \(N(N-1)/2 \approx 2\times 10^{10}\) で、Python の int なら安全に扱えます。

  ソースコード

import sys

class Fenwick:
    __slots__ = ("n", "bit")
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def add(self, i, x):
        n = self.n
        bit = self.bit
        while i <= n:
            bit[i] += x
            i += i & -i

    def sum(self, i):
        s = 0
        bit = self.bit
        while i > 0:
            s += bit[i]
            i -= i & -i
        return s

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

    fw = Fenwick(N)
    inv = 0
    seen = 0
    for x in P:
        leq = fw.sum(x)
        inv += seen - leq
        fw.add(x, 1)
        seen += 1

    ans = inv - K
    if ans < 0:
        ans = 0
    print(ans)

if __name__ == "__main__":
    main()

---

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