AOJ 反転数（転倒数）BITによる高速化

今回は反転数について扱っています。転倒数とも呼ばれるようです（というより競プロ界隈では転倒数の方が一般的かも？）。

問題へのリンク

反転数とは

数列があるとき、 のとき となるの組みの数。

つまり、ある数より左側にいくつより大きい数があるかを数えられればよい。

方針

愚直にO(N²)

全て試せばいいです。ただこれだと間に合いませんね。

高速化、O(NlogN)

方針転換

ここで、より大きい数を数えるのではなく、以下のものを数え、全体から引くことで目的を達成します。つまり、より左側にいくつ自分以下のものがあるかを高速に数えることを考えます。

準備

1. 実際にの大小を比較してもいいのですが、配列の長さがだけ必要になってしまい制約によっては困るので、がソートしたときに移るindex(とする）を保存しておくことにしましょう。ソート後のindexさえわかればその大小関係を知るのに十分ということです。

2. 数列Aを前から見ていきます。あるindexが出てきた個数は数列に保存しておきましょう。

数列の中に、以下のものがいくつあるかを高速に求めたいです。つまり、数列のprefixの和がほしいということです。Range Sum Queryですね。Range Sum Queryはセグ木、BIT（Binary Indexed Tree）などのデータ構造で解くことができるので、利用しない手はないです。をBITに埋め込んで、prefixの和を求められれば、この問題をで解くことができました。

実装

提出のリンク

#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)
#define print(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<_<<", "; cerr<<"]"<<endl; }

typedef long long ll;
template<typename T>
class BIT{
  public:
    int N;
    vector<T> data;
    BIT(T _N):N(_N){
        data.assign(N+1, 0);
    };
    
    // a is 1-indexed
    void add(int a, T w){
        for(int x = a; x <= N; x += x & -x)data[x] += w;
    }
    // 1-indexed sum of prefix [0, a]
    T sum(int a){
        T res = 0;
        for(int x = a; x > 0; x -= x & -x)res += data[x];
        return res;
    }
    // 1-indexed sum of range [l, r]
    T sum(int l, int r){return sum(r) - sum(l-1);}

    // 0-indexed add
    void add0(int a, T w){add(a + 1, w);}
    // 0-indexed sum
    T sum0(int a){return sum(a + 1);}
    // 0-indexed sum of range
    T sum0(int l, int r){return sum0(r) - sum0(l-1);}
    // show the value
    void debug(){print(data);}
};


int main() {
    int N;
    cin >> N;
    vector<ll> a(N),b(N);
    vector<pair<ll, int>> ap;
    rep(i,N){
        cin>>a[i];
        ap.push_back(make_pair(a[i], i));
    }
    sort(ap.begin(), ap.end());
    rep(i,N)b[ap[i].second] = i;
    BIT<long long> c(N);
    ll ans = 0;
    rep(i,N){
        ans += i - c.sum0(b[i]);
        c.add0(b[i], 1);
    }
    cout << ans << endl;
}