平方分割でこの問題を解くこともできます。

ブロックサイズを \(B\) として、あらかじめ配列を長さ \(B\) ごとのブロックに分けそれぞれのブロックごとに出現する値ごとの出現回数を記録しておきます。 各クエリでは、区間に完全に含まれるブロックごとに記録した出現回数を加算し、完全に覆われていない箇所は愚直に出現回数を数えます。完全に含まれるブロックの数は高々 \(O(N / B)\) 個、愚直に数え上げる箇所の数は高々 \(O(B)\) 個であるので、全体で \(O(Q(N / B + B))\) でこの問題を解くことができます。特に \(B = \sqrt{N}\) とすると \(O(Q \sqrt{N})\) で解くことができます。

実行時間制限が厳しいため、PythonなどではACは難しいかもしれません。

実装例（C++）