平方分割による別解を紹介します。 こちらの方が実装は楽かもしれません。

要素 \(i\) の数列の中での頻度を \(C_i\) と置くと求める答えは \(\displaystyle\sum \dfrac{C_i \times (C_i - 1)}{2} \) です。

クエリの処理で \(C_i\) の増減を見れば、差分を管理することで答えが求まります。 数列を長さ \(B\) のブロック \(\dfrac{N}{B}\) 個に分割します。クエリ \([l, r]\) に対して、

A: 完全に内包されているブロック

• ブロック内の要素がすべて同じ場合

  • \(O\left(1\right)\) で処理することができます。

• そうでない場合

  • \(O\left(B\right)\) で処理し、ブロック内の要素がすべて同じになったというフラグを立てます。

B: 一部だけ重なっているブロック

• \(O\left(B\right)\) で処理し、ブロック内の要素がすべて同じというフラグを外します。

A で \(O\left(B\right)\) で処理する必要のあるブロックはクエリ毎で高々二つしか増えず、一度 \(O\left(B\right)\) で処理すると B で引っかかるまでは \(O\left(1\right)\) で処理できることから、全体で \(O\left(N + QB + QN/B\right)\) で解くことができます。

\(B = \sqrt{N}\) とすることで、\(O\left(N + Q\sqrt{N}\right)\) が達成可能です。