この問題は、\(\Theta(N + Q)\) 時間で解くことができます。

「\(A_L, \dots, A_R\) の中の \(X\) の個数」を、「\(X\) を \(1\) 、それ以外を \(0\) に変換したときの区間和」と考えると、累積和が使えそうです。

累積和 : \(\text{sum}[X][i] = {}\)(\(A_1, \dots, A_i\) の中の \(X\) の個数) とすると、答えは \(\text{sum}[X][R] - \text{sum}[X][L - 1]\) です。

しかし、このままでは \(X = 1, \dots, N\) のそれぞれについて累積和を求める必要があり、\(\Theta(N^2)\) 時間かかってしまいます。

ここで、\(i = 0, \dots, N\) の順に走査し、累積和 : \(\text{sum}[X] = {}\)(\(A_1, \dots, A_i\) の中の \(X\) の個数) を更新していくと、更新は \(\Theta(N)\) 時間で行えます。

よって、累積和が必要になる位置 \((X, R), (X, L - 1)\) をバケットソートすることで、\(\Theta(N + Q)\) 時間で解くことができました。

実装例 (C++)