No.742
数直線を正の向きに移動する猫と負の向きに移動する猫と動かない猫に分けて考える.
正の向きに動く猫および動かない猫 \(i\) が \(j \ (j \lt i)\) の猫と出会うかどうかを考える.
-
正の向きに動く猫 \(j\) のうち, \(M_j \gt M_i\) の猫に出会う.
-
動かない猫および負の向きに動く猫には出会わない.
負の向きに動く猫 \(i\) が \(j \ (j \lt i)\) の猫と出会うかどうかを考える.
このときは, \(M_j \gt M_i\) の猫に出会う.
よって, Fenwick Tree を使って猫の数を管理しておけばいい.