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 翻译