転倒数
反転数、もしくはInversion Numberとも。数列$ \{a_i\}において、$ a_i \gt a_j\,(1 \le i \lt j \le n)となる$ (i, j)の組の数のこと。バブルソートの交換の回数になることでも知られている。
求めかたは2つあり、1つはBITをつかう方法で、もう1つはマージソートをつかう方法。前者については、サイズ$ \max a_i のBITを用意しておき、$ \{a_i\} を前から見ていってそれぞれの位置$ a_i の要素に$ 1 を足すという操作を繰り返すことを考えればよい。このとき、区間$ [i + 1, \max a_i] の総和がいままでに登場した$ a_iよりも大きい要素の個数になる。コードで書くとつぎのようになる。なお、BinaryIndexTreeは与えられているものとする。 code:java
long ans = 0;
BinaryIndexTree bit = new BinaryIndexTree(maxA);
for (int i = 0; i < n; i++) {
ans += i - bit.query(ai); }