2値配列における転倒数の求め方(計算量O(n))

　AGC034_Bのような問題で、2値配列の転倒数を求めることがあったが、大抵解説では流されていることが多いためメモ。
　転倒数とはなにかはここ)。ここでは後の説明のために「バブルソートを行うときにswapを行う回数」としておく。

　転倒数を求める場合、多値配列ではBITやセグメントツリーなどを用いて計算するが、2値配列の場合はそんなに大掛かりなものは必要なくて、更に左から順番に見ることで O(n) でOKになる。
　用意するのは以下の2つの配列。

• count[i] ・・・0からi番目までに、2値で比較が後ろ側になる値の数
• inv[i] ・・・・0からi番目までの転倒数

　最終的に求めたいのはinv[n]で、この2つの配列を左から更新していく。

　まず0番目には何も無いとして count[0] = 0、inv[0] = 0 として初期化する。
　次に、元の配列のi番目が2値のどちらかで場合分けしてこの2つの配列を更新する。　　

1. 元配列のi番目が2値のうち比較で後ろ側の場合
   　この場合は転倒数は増加しない(一番うしろにあるため)ので inv[i] = inv[i - 1] 。
   　countは1増えるため count[i] = count[i - 1] + 1 。

2. 元配列のi番目が前に来る方の場合 　countは増加しないため count[i] = count[i - 1]。
   　ここで、i-1番目までの配列がすでにソートされている状態を考えると、i番目にある数をcount[i]分前に持っていかなければならない。そのため、更新は inv[i] = inv[i - 1] + count[i - 1] となる。

　あとはこの2つの場合をつかった更新を前から順番にnまで行えば答えが出る。計算量は普通に O(n)。