概要

順列に対して「隣り合う2人の交換」をちょうど \(K\) 回行ったあと、転倒数（\(i<j\) かつ \(P_i>P_j\) となる組の個数）として達成できる最小値を求める問題です。

考察

まず重要な事実として、隣り合う2つの要素を1回交換すると、転倒数はちょうど \(1\) だけ増えるか、\(1\) だけ減るか、のどちらかになります。

• 交換する2人について \(P_i > P_{i+1}\) なら、その組が解消されるので転倒数は \(1\) 減る
• 逆に \(P_i < P_{i+1}\) なら、新たに逆順の組が生まれるので転倒数は \(1\) 増える

他の位置との関係は交換によって変化しないため、1回の操作で転倒数の変化量は必ず \(\pm 1\) です。

ここで初期状態の転倒数を \(T\) とおきます。考えるべきは「ちょうど \(K\) 回」操作した後に到達できる転倒数の最小値です。

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

転倒数を減らす操作（逆順の隣接ペアを交換）を毎回選べば、\(K\) 回で転倒数を \(T - K\) まで下げられます。\(K \le T\) なら減らす操作が必ず存在し続けるので、最小値は \(T - K\) です。

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

転倒数は最小でも \(0\)（完全にソート済み）です。\(T\) 回かければ転倒数を \(0\) にできますが、まだ操作回数が \(r = K - T\) 回残ります。

残りの操作も「ちょうど」行わなければならない点がポイントです。転倒数 \(0\) の状態からは増やすことしかできませんが、同じペアを2回交換すれば元に戻るため、転倒数の偶奇に注目します。

• \(r\) が偶数なら、適当な隣接ペアを「交換→戻す」を繰り返すことで転倒数 \(0\) を保てる → 答えは \(0\)
• \(r\) が奇数なら、最後に1回分だけ余計な交換が残り、転倒数 \(0\) にはできない → 最小は \(1\)

このように、転倒数の変化が常に \(\pm 1\) である（=パリティが操作回数ごとに反転する）という性質が鍵になります。

素朴なアプローチの問題点

転倒数 \(T\) を二重ループで数えると \(O(N^2)\) となり、\(N \le 2\times10^5\) では間に合いません。また \(K \le 10^{18}\) と非常に大きいので、操作を1回ずつシミュレーションするのも不可能です。上記の考察により、実際にシミュレーションせず \(T\) と \(K\) の関係だけで答えが決まることを利用します。

アルゴリズム

1. 転倒数 \(T\) の計算: BIT（Binary Indexed Tree / フェニック木）を使い、左から順に要素を追加しながら「すでに追加済みの値のうち、現在の値より大きいものの個数」を足し合わせていきます。これで \(O(N\log N)\) で転倒数が求まります。
2. 場合分け:
   • \(K \le T\) なら答えは \(T - K\)
   • \(K > T\) なら \(r = K - T\) として、\(r\) が偶数なら \(0\)、奇数なら \(1\)

計算量

• 時間計算量: \(O(N \log N)\)（BIT による転倒数計算が支配的）
• 空間計算量: \(O(N)\)

実装のポイント

• \(K\) や転倒数 \(T\) は最大で \(\frac{N(N-1)}{2} \approx 2\times10^{10}\) や \(K \le 10^{18}\) に達するため、必ず64bit整数（long long）で扱います。

• BIT で「自分より大きい値の個数」を求めるには、すでに追加した個数 \(i\) から「自分以下の値の個数 sum(v)」を引きます（i - sum(v)）。値は \(1\) から \(N\) なので、そのまま BIT のインデックスとして使えます。

• 場合分けは \(T\) と \(K\) の大小比較と、\(r=K-T\) の偶奇判定だけというシンプルな実装になります。

  ソースコード

#include <bits/stdc++.h>
using namespace std;

int main(){
    int N;
    long long K;
    scanf("%d %lld", &N, &K);
    vector<int> P(N);
    for(int i=0;i<N;i++) scanf("%d", &P[i]);
    
    // inversion count using BIT
    vector<long long> bit(N+1, 0);
    auto add=[&](int i){ for(; i<=N; i+= i&(-i)) bit[i]+=1; };
    auto sum=[&](int i){ long long s=0; for(; i>0; i-= i&(-i)) s+=bit[i]; return s; };
    
    long long T=0;
    for(int i=0;i<N;i++){
        int v=P[i];
        // count of already added values greater than v
        // already added = i elements, those <= v = sum(v)
        long long less_eq = sum(v);
        T += (long long)i - less_eq;
        add(v);
    }
    
    long long ans;
    if(K <= T){
        ans = T - K;
    } else {
        long long r = K - T;
        ans = (r % 2 == 0) ? 0 : 1;
    }
    printf("%lld\n", ans);
    return 0;
}

---

この解説は claude4.8opus-high によって生成されました。