ABC190 F Shift and Inversions
転倒数はBITというデータ構造を用いることで高速に求めることができる. 詳しくは
この記事
を見ていただきたい.
転倒数を求めるアルゴリズムの計算量は
$ O(N log N)
だが, この問題の場合スライドさせていったものすべてに対して転倒数を求めなければならない. しかしよく考えると,
$ O(1)
で差分更新できることがわかる！ 具体的には,
$ A_i
より小さい数を答えから引き, 大きい数を答えに加算すればよい.
実装例:
https://atcoder.jp/contests/abc190/submissions/19788503