分数: 475 点
问题陈述
给你一个整数序列 给出了 A = (A_1, A_2, \ldots, A_N) 长度 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 作为答案。
约束
- 1 \leq N, Q \leq 3 \times 10^5
- 1 \leq A_i \leq 100
- 1 \leq L_i \leq R_i \leq N
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
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
5 4 2 1 3 3 1 2 4 1 4 1 5 3 3
示例输出 1
24 44 74 3
我们解释第一个查询。
要计算的值为 \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.