Inversion Queries

解説

この問題はMo's algorithmとFenwick treeで解くことができます。

区間$[L,R)$の転倒数が分かっている時、

• $R+1$と加える時、$A[R]$より大きい要素の数を答えに加える
• $R-1$と削除する時、$A[R]$より大きい要素の数を答えから引く
• $L+1$と削除する時、$A[L]$より小さい要素の数を答えから引く
• $L-1$と加える時、$A[L]$より小さい要素の数を答えに加える

これらの操作により答えが求まります。

計算量はMo's algorithmが$O(N\sqrt{Q})$、区間を広げる処理に$O(\log{\max(A_i)})$より、全体で$O(N\sqrt{Q} \log{ \max(A_i) })$となります。

実装