転倒数を求める実装をライブラリ化した

要求される度に、uniqueやらeraseやら、1-indexやらの箇所で微妙に考えてしまうので、この際ライブラリ化しておく。

※ 転倒数には、i < j でかつ、a_i > a_j であるとき転倒とする場合と、a_i >= a_j であるとき転倒とする場合の2種類があり、以下の実装は前者のものに対応する。

前提

• 転倒数は素直に実装すると、数列の長さをnとして、O(n²)
• BITを活用することで計算量をO(n log n)に改善できる
• 先頭から要素を見ていきながら、ループの中ではざっくり2つのことを行っている
  1. 今の要素値 a_ i 以下の個数をBITを用いてカウントする
     • 今の添え字i - ↑の個数 = a_i を末尾に追加することで生じる転倒数
  2. BITに要素 a_i を登録する

実装上での注意点

• 扱う数列の要素値が正で最大値が小さい場合（10⁵とか）なら、要素の取り得る最大値をBITの長さとして取ればよい。
  • 例えば数列の長さがnで、要素が1~nの連続した値になっている場合がそう。
• 問題によっては、要素の最大値が10¹⁸などになっており、これをそのままBITの要素数とすると空間計算量オーバーとなる場合がある。（以下に載せた検証用問題がそう）
• その対策として以下の実装では一次元座標圧縮を行っている
  • 今見ている要素が全体で何番目に大きいか（rank）で要素を各管理すればBITのサイズは数列の要素数だけで済む

検証用問題

onlinejudge.u-aizu.ac.jp

実装

※ 要 Binary Index Tree

pione.hatenablog.com

/// 転倒数
long long inversion_number(const vector<long long>& v){
  auto u=v;
  sort(u.begin(), u.end());
  u.erase(unique(u.begin(), u.end()), u.end());
  
  auto bit=BIT<long long>(u.size());
  
  long long res=0;
  for(int i=0; i<v.size(); i++){
    int rank=lower_bound(u.begin(), u.end(), v[i])-u.begin()+1;
    res+=i-bit.sum(rank);
    bit.add(rank);
  }
  return res;
}

座標圧縮の実装に関する個人的なメモ

座標圧縮の実装箇所において、地味に実装バグのトラップとなる箇所があるのでメモしておく。

1. unique 呼び出し前には必ずソート

未ソートの状態でもuniqueは当然呼び出し可能だが、この場合、隣り合った重複要素だけが取り除かれる。

つまり、↓のように完全に重複が除去されない可能性がある。

a a a a a b b b b b a => a b a

cpprefjp.github.io

2. erase の引数

  u.erase(unique(u.begin(), u.end()), u.end());

上記のeraseは↓のように第二引数を忘れてもコンパイルが通ってしまう。

  u.erase(unique(u.begin(), u.end()));

この場合のeraseの挙動は、uniqueが返す index の1つの要素のみを削除する。

1 or 2 のミスを犯すことで、重複が完全に除去されずに残ってしまい、後の二分探索が正常に動作せずバグが生じる。