第一回日本最強プログラマー学生選手権-予選- B Kleene Inversion
Diff 801.
Bの
$ i
番目の
$ A
を
$ C_i
という数列とする.
$ C_i
の各要素について,
$ C_{i-1}
までと
$ C_i
内に分けて考える.
$ C_{i-1}
までの要素を考えたときの転倒数は全体を見ると等差数列の形になっているので簡単な計算によって
$ O(N^2)
で求めることができる.
$ C_i
内については愚直に計算していけばよい.
実装例:
https://atcoder.jp/contests/jsc2019-qual/submissions/18987886