ABC190 F - Shift and Inversions (600)
転倒数はセグ木やBITを用いて$ O(N \log N)で求められる
愚直に毎回求めていると全体で$ O(N^2 \log N)になりTLEする
毎回の差分について考える
最初の要素が最後に回ると
最初の要素より小さい数の数だけ転倒数が減少
最初の要素より大きい数の数だけ転倒数が増加
配列$ Aは並び替えされているだけなので、自身より小さい数の数はそのまま得ることができる
初回の転倒数を求めた後は回転毎に$ O(1)で差分が求められるので全体で$ O(N \log N)