座標圧縮とBITで転倒数（反転数）を求める

Quiz

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_D&lang=jp

Submit

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3579423#1

座標圧縮とは

• 大小関係を保ったまま、値のスキマをなくすことで値域を減らす
• 例 [1, 100, 10000] => [0, 1, 2]

BIT (Binary Indexed Tree)とは

• 配列 a1〜aNにて、
  • aiにxを足す
  • a1〜aiまでの和を求める
• を高速にO(logN)で行うデータ構造

転倒数（反転数）

• バブルソートで必要な最小の交換回数
• 例：[3 5 2 1 4] の反転数は、6
  • 3, 2
  • 3, 1
  • 5, 2
  • 5, 1
  • 5, 4
  • 2, 1

本問題について

• 想定解は分割統治法のようだ
• BITだけでは値域が広いのでTLE
• 座圧すればいける

転倒数・反転数の求めかた

auto bit = BinaryIndexedTree<ll>(N);

ll count = 0;
FOR(i, 0, N){
    ll a = A[i];
    ll num = i - bit.sum(a); // aより先に出現した、aよりも大きい数の個数
    count += num;
    bit.add(a, 1);
}

転倒数の計算量

• 値域の幅をAとして、O(A log A)

ライブラリ

• BITはこちらからお借りしました。感謝
• https://ei1333.github.io/luzhiled/snippets/structure/binary-indexed-tree.html

類題

https://yukicoder.me/problems/no/742