【ABC190】F - Shift and Inversions

atcoder.jp

解法

k=0の時は元の数列のまま、転倒数を求めればよい。
愚直に求めようとするとO(N²)になるが、BITを使うとO(NlogN)で求めることができる。
具体的には、下の記事がわかりやすい。

scrapbox.io

あとはk=1~N-1の時を考えればよいが、k=iからk=i+1に変化するとき、

1、先頭のa[i]が削除される
2、Aの末尾にa[i]が追加される
という2つの操作が行われる。

操作1によって、転倒数はa[i]だけ減る。
また、操作2によって、転倒数はN-a[i]-1だけ増える。
これで、O(1)で転倒数の変化を求めることができた。

実装

struct BIT {
    int n;
    vector<ll> bit;
    BIT(int n_) : n(n_ + 1), bit(n, 0) {}
    void add(int i, ll x) {
        for (int idx = i; idx < n; idx += (idx & -idx)) {
            bit[idx] += x;
        }
    }
    ll sum(int i) {
        ll s = 0;
        for (int idx = i; idx > 0; idx -= (idx & -idx)) {
            s += bit[idx];
        }
        return s;
    }
};

void solve(long long N, std::vector<long long> a){
    auto tree = BIT(N);

    ll cnt = 0; // 転倒数
    REP (i, N) {
        cnt += i-tree.sum(a[i]+1);
        tree.add(a[i]+1, 1);
    }

    c(cnt)
    REP (i, N-1) {
        cnt += N - a[i] - 1;
        cnt -= a[i];
        c(cnt)
    }
}