AT_abc423_e.[ABC423E] Sum of Subarrays

给定一个长度为 $N$ 的整数序列 $A = (A_1, A_2, \ldots, A_N)$。

有 $Q$ 次询问，请你分别求出每一次询问的答案。

在第 $i$ 次询问中，给定整数 $L_i$ 和 $R_i$，请你计算 $\displaystyle\sum_{l = L_i}^{R_i}\sum_{r = l}^{R_i}\sum_{j = l}^{r} A_j$ 作为本次询问的答案。

输入按以下格式由标准输入给出：

$ N $ $ Q $

$ A_1 $ $ A_2 $ $ \ldots $ $ A_N $

$ L_1 $ $ R_1 $

$ L_2 $ $ R_2 $

$ \vdots $

$ L_Q $ $ R_Q $

输出共 $Q$ 行。第 $i$ 行输出第 $i$ 次询问的答案。

样例解释 1

这里解释第一个询问。

需计算的值为 $\displaystyle\sum_{l = 2}^{4}\sum_{r = l}^{4}\sum_{j = l}^{r} A_j$。

• 当 $l = 2, r = 2$ 时，$\displaystyle\sum_{j = l}^{r} A_j = 1$。
• 当 $l = 2, r = 3$ 时，$\displaystyle\sum_{j = l}^{r} A_j = 4$。
• 当 $l = 2, r = 4$ 时，$\displaystyle\sum_{j = l}^{r} A_j = 7$。
• 当 $l = 3, r = 3$ 时，$\displaystyle\sum_{j = l}^{r} A_j = 3$。
• 当 $l = 3, r = 4$ 时，$\displaystyle\sum_{j = l}^{r} A_j = 6$。
• 当 $l = 4, r = 4$ 时，$\displaystyle\sum_{j = l}^{r} A_j = 3$。

由上可得，要求的值为 $(1 + 4 + 7) + (3 + 6) + 3 = 24$。

数据范围

• $1 \leq N, Q \leq 3 \times 10^5$
• $1 \leq A_i \leq 100$
• $1 \leq L_i \leq R_i \leq N$
• 所有输入值均为整数。

由 ChatGPT 5 翻译