各 \(A_j\) に対し、式 \(\displaystyle\sum_{l = L_i}^{R_i}\sum_{r = l}^{R_i}\sum_{j = l}^{r} A_j\) で \(A_j\) が足される回数を考えます。

\(j < L_i\) または \(R_i < j\) のときは \(A_j\) は足されないので、\(L_i \leq j \leq R_i\) なる \(j\) についてのみ考えます。

\(A_j\) は \(l \leq j \leq r\) のとき \(1\) 度ずつ足されるので、\(A_j\) が足される回数の合計は \(L_i \leq l \leq j \leq r \leq R_i\) を満たす整数組 \((l, r)\) の数に等しいです。

\(L_i \leq l \leq j\) なる整数 \(l\) は \(j - L_i + 1\) 個、\(j \leq r \leq R_i\) なる整数 \(r\) は \(R_i - j + 1\) 個であることから、上の条件を満たす整数組 \((l, r)\) の個数は \((j - L_i + 1)(R_i - j + 1)\) です。

したがって、求める式の値は \(\displaystyle\sum_{j = L_i}^{R_i} (j - L_i + 1)(R_i - j + 1)A_j\) であり、展開すると \(\displaystyle\sum_{j = L_i}^{R_i} -j^2A_j + (L_i + R_i)jA_j + (-L_i + 1)(R_i + 1)A_j\) となります。

これにより、クエリが \(1\) つの場合は上式を用いて \(O(N)\) 時間で計算できます。

\(Q\) 個のクエリに対応するためには、\(j^2A_j, jA_j, A_j\) の累積和を持っておき、区間和を取ったのちに係数を掛け合わせて和を取ればよいです。