平方分割解法を紹介します。

\(L=1\) の場合のみを考えれば十分です。このときの答えを \(f(R,X)\) とします。

\(R\) が固定のとき

\(R\) が固定されたクエリしか来ない問題を考えてみます。このとき、\(X\) を動かして \(f(R,X)\) が変化するのは、\(X\) が \((A_i)\) に含まれるいずれかの値をまたぐときに限ります。

例えば \(A=(1,3,4,7,7)\) のとき、\(X=0,1,2,3,\ldots\) に対する \(f(5,X)\) は \(0,1,1,4,8,8,8,22,22,22,22,\ldots\) となります。

よって、各 \(f(R, A_i)\) を予め計算し、組 \((A_i,f(R,A_i))\) を保持しておくことで、二分探索により \(f(R,X)\) には \(O(\log R)\) で答えることができます。
全ての \(i\) についての \(f(R,A_i)\) を求めることは、\(A\) をソートすることで \(O(R\log R)\) でできます。

元の問題

\(R\) が動く元の問題に戻ります。
\(g(M,X)\) がわかっているとき、\(g(R,X)\)を計算することは愚直に \(A_{M+1},A_{M+2},\ldots,A_R\) を調べることで\(O(R-M)\) でできます。よって 適当な \(B\) をとり、全ての \(k\) について、\(R=kB\) と固定した場合に対する問題の前計算をしておけば、\(f(\left\lfloor\frac{R}{B}\right\rfloor B,X)\) を求めたあと残りを愚直に計算することでクエリあたり \(O(B+\log N)\) で求めることができます。

\(R\) を固定した場合に対する問題の前計算には \(O(R\log R)\) かかることから、前計算全体には \(\sum_{kB\leq N}O(kB\log kB)=O(\frac{N^2}{B}\log N)\) かかります。
よってこの問題は全体で \(O(\frac{N^2}{B}\log N+Q(B+\log N))\) で解くことができます。\(B=\Theta(N\sqrt{\frac{\log N}{Q}})\) とすることで \(O(N\sqrt{Q\log N}+Q\log N)\) でこの問題 を解くことができます。

高速な言語であれば実行時間制限に間に合わせることができます。

実装例(C++)
B=3000 (1400ms)
B=5000 (1400ms)
B=7000 (1600ms)

おまけ

この解法はほとんどそのままセグ木に乗せることができ、マージソートの要領で計算することで、前計算 \(O(N\log N)\) クエリ \(O((\log N)^2)\) にできます。それが公式解説です。