atcoder.jp 解法 k=0の時は元の数列のまま、転倒数を求めればよい。 愚直に求めようとするとO(N2)になるが、BITを使うとO(NlogN)で求めることができる。 具体的には、下の記事がわかりやすい。 scrapbox.io あとはk=1~N-1の時を考えればよいが、k=iからk=i+1…

問題のリンク 本当はAtCoder Libraryを使って解くことが想定されている問題ですが、全く使わず解きました。 とりあえずなんでもいいので、遅延評価セグメント木の練習がしたかったので。 転倒数について まず、これがわからないと問題が解けません。 一応問…