転倒数

転倒数 とは 【検索】

数列で、

「左にあるくせに大きいやんけ！(ソートされてるなら左に小さいのが来るはずなのに…)」

ってなってる組の数。バブルソートの交換回数にもなる。

{1,2,3,4,5}の転倒数は0

BITで転倒数を求めてみる

BITとは？

一点加算、1~N番目までの区間和をどちらもlogで計算できる便利なデータ構造

転倒数を求める手順

左から順番に、「自分より左にいるのに自分より大きい数」の個数を足していった時の総和が転倒数。

BITで出席をとる

左から順番にBITを使って、「4が登場したからBITの4番目の所に1を足す…」「2が出てきたからBITの2番目に1足す…」みたいな作業を左から順番にしていきます。出席を取る感じに似てますね…！

注意：BITは1-indexedです

table:最初の状態

A: 8 3 6 5 2 4 1 9 7

BIT:

table:8が出てきたのでBITの8番目に1を足した

A: |8| 3 6 5 2 4 1 9 7

BIT: 1

table:3が出てきたのでBITの3番目に1を足した

A: 8 |3| 6 5 2 4 1 9 7

BIT: 1 1

table:6が出てきたのでBITの6番目に1を足した

A: 8 3 |6| 5 2 4 1 9 7

BIT: 1 1 1

table:5が出てきたのでBITの5番目に1を足した

A: 8 3 6 |5| 2 4 1 9 7

BIT: 1 1 1 1

table:2が出てきたのでBITの2番目に1を足した

A: 8 3 6 5 |2| 4 1 9 7

BIT: 1 1 1 1 1

https://gyazo.com/ecefa1ff41cb2d997d3193d4de331b78

ここで4から見た「左にあるのに自分より大きい数 = {8,6,5}」の個数(つまり3つになる)を数えてみましょう。

なんとBITの4より右にある数字の合計がその個数になります！！

https://gyazo.com/de8138097c1ff14d7badf884ffef0ebf

それはなぜですか

配列を4の手前まで見たときにBITに1が書かれた数字は「4より左にある数字」

BITで4より右側に1が書かれている数字→「4より大きい数字」

BITの右側（今見ている数字より大きい所）に書かれている1をすべて足せば、それは「4より左にあって、4よりも大きい数字の個数」になる

で、これをどうやったらBITで計算できるのかというと、引き算を使います。

今、BITの配列上にある値( 11 11 1 )の総和は、これまでに見てきた数字の個数と等しいです(上の画像だと、それまでに5個見てきたので総和も5になります)。その総和から自分より値が小さい数字(上画像斜線部)の個数を引けば、右にある数字の個数を求めることができます。つまり

全体 - 左にある個数 ＝ 右にある個数

ということです。BITは、1~N番目までの総和を計算するのが得意なので、今回の場合だと、

5 - (1~4までの総和) = 5 - 2 = 3

という風に計算できます。やった〜。

実装例

code:転倒数.cpp

using namespace std;

typedef long long int ll;

// 1-indexedなので注意。

struct BIT {

private:

vector<int> bit;

int N;

public:

BIT(int size) {

N = size;

bit.resize(N + 1);

}

// 一点更新です

void add(int a, int w) {

}

// 1~Nまでの和を求める。

int sum(int a) {

int ret = 0;

return ret;

}

};

// ====================================================================

int main() {

int n;

cin >> n;

vector<int> v(n);

ll ans = 0;

BIT b(n); // これまでの数字がどんな風になってるのかをメモる為のBIT

for (int i = 0; i < n; i++) {

}

cout << ans << endl;

}