← 返回题目列表

AtCoder · abc423_e

E. 子数组之和

中文机器翻译题面 查看原题

分数: 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.