perogram

座標圧縮と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

f:id:peroon:20200105081735p:plain

本問題について

  • 想定解は分割統治法のようだ
  • 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);
}

f:id:peroon:20200105082339p:plain

転倒数の計算量

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

ライブラリ

類題

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