Atcoder水色精進記録
ABC396
F - Rotated Inversions
https://atcoder.jp/contests/abc396/tasks/abc396_f
アルゴリズム・データ構造
SegTree, FenwickTree
考察
N,Mが2*10**5なので
愚直な全探索は負荷
Kの値に対して、O(1)orO(logN)くらいの計算が必要そう
→事前に何か計算しておくか、差分のみ考えることができないか。
K=0の時の転倒数はO(N)でカウントできる？
現在のiより左にAiより大きい値の数を覚えておく必要がある。
各数字の出現数を管理することでできる？
→普通に管理すると最大i-1個の数字を確認することになるのでO(N**2)となる。
→SegTreeで管理することでO(NlogN)で行けそう。
K=1になったらどう変わる?
Ai+KがMになる場合、0になり、他の要素との転倒関係が変わる
M未満に場合、他の要素も全て＋1されるため転倒関係は変わらない
Ai+Kが0になった場合、
その要素より左側は全て転倒数に加算する必要がある。(同時に0になったものは注意)
(1loop前はその要素が最大なので、その要素より左側の数は全てその要素より小さい)
その要素より右側は同じ値となる要素以外は転倒で無くなる
(1loop前はその要素が最大なので、その要素より右側は全て転倒count)
差分に着目するとO(1)で計算できそう。
提出
感想
Segtreeを使って無駄なことをしていたら定数倍でギリギリTLEとなった。
FenwickTreeだと無駄なことをしていてもかなり余裕を持ってACとなった。
https://atcoder.jp/contests/abc396/submissions/64677680
FenwickTreeでいい場合はこちらの方が安全(特にpythonだと)なので、FenwickTreeを空で描けるようになる必要がある。