バブルソートと転倒数
基本
バブルソートの交換回数=転倒数 転倒数はBITを使って簡単に求められます（BITは区間和をO(logN)で求められるデータ構造です）。以下そのアルゴリズムを述べます。 与えられた数列xの要素を左から順番に見ていくことにして、要素a, b(a<b)が転倒している（つまりソート前の順列ではb aの順に現れるという事です）としたとき、この転倒は要素aを考えているときに加えることにします。つまり要素aを見ているときaより左側にあり、かつaよりも大きいような要素の数を足していくことにします。左から要素を見ていくのと同時に、見終わった要素をBITに追加していくことによって以上の操作を高速に行えます。具体的にはBIT.add(a, 1)をaを見終わった後に行い、BIT.sum([i, n))を答えに加えていきます。ただしiはaのインデックスです。 逆にs = [0, 1, 2, 3・・・, n]を左から見ていくという考え方もあります。つまりbitにaのインデックスを追加していくということです。ただxとsを入れ替えただけだとも言えますが...
応用
転倒数はdpと相性がいいです。どうしてかというと上で述べたようにある要素aに関する転倒数を考えているとき、aより大きい、かつaより左にある要素の数がもとめられればいいわけですが、これはaより左の並び方に関係なくaの位置と値のみに依存するからです。 これを使うのが以下の問題です。 E - Sorted and Sorted
その他
任意の数列a, bの間の転倒数は片方を0, 1, 2, 3・・・に直すのがいい。 同じ要素が複数ある場合はその要素間での交換が起きないようにするのが交換回数を最小にする。 E - Papple Sort
