F - Multiplayer Rock-Paper-Scissors

$f(g, c, p)$ を、グーが $g$ 人、チョキが $c$ 人、パーが $p$ 人のときの勝ち手（引き分けなら $D$）を返す関数とします。この関数自体は $O(1)$ で計算できます。

クエリ $i$ について、$L_i, \ldots, R_i$ 番目の人のうち、グーを出した人の人数を $g$、チョキを出した人の人数を $c$、パーを出した人の人数を $p$ とします。

あなたがグーを出したときに大人数じゃんけんに勝てるかどうかを考えます。このとき、$f(g + 1, c, p)$ が $G$ ならば勝つことができます。なぜならば、$L_i, \ldots, R_i$ 番目の人とあなたのうち、グーを出した人の人数は $g + 1$ 人で、チョキ・パーを出した人の人数はそれぞれ $c$、$p$ だからです。 同様に、$f(g, c + 1, p)$ が $C$ ならばチョキを出したときに勝つことができ、$f(g, c, p + 1)$ が $P$ ならばパーを出したときに勝つことができます。

これより、$L_i, \ldots, R_i$ 番目の人のうち、グー・チョキ・パーをそれぞれ出す人の人数を高速にもとめられればこの問題を解くことができます。これは累積和を使うことで $O(1)$ で求めることができます。