ABC293 G - Triple Index (600)
コンテスト中の考察
愚直に解くと$ \mathcal{O}(NQ)
登場回数の累積和を取っても意味が無い
平方分割をしようにも結局登場回数を全ての位置で記憶する必要があり駄目
解説の解法
Mo's algorithmで解く
$ B = \max\left(1, \frac{N}{\sqrt{Q}} \right)とする
区間クエリを以下の順で並び替える
$ \frac{l}{B}の昇順
同じ場合は$ rの昇順
後はこの順番でクエリを状態を持ちながら解いていく
$ l,rを移動するタイミングでその数が指している値の組の数を更新する
個数は$ \frac{v(v-1)(v-2)}{6}になるので、今の値が外れるときは引いてから足し、入るときは足してから引く
全体で$ \mathcal{O}(N\sqrt{Q})になる