AtCoder Beginner Contest 423
翻译中…
Problem Statement
翻译中…
You are given an integer sequence $A = (A_1, A_2, \ldots, A_N)$ of length $N$.
翻译中…
$Q$ queries are given, so find the answer for each.
翻译中…
In the $i$-th query, integers $L_i$ and $R_i$ are given, so find $\displaystyle\sum_{l = L_i}^{R_i}\sum_{r = l}^{R_i}\sum_{j = l}^{r} A_j$ as the answer.
翻译中…
Constraints
翻译中…
$1 \leq N, Q \leq 3 \times 10^5$$1 \leq A_i \leq 100$$1 \leq L_i \leq R_i \leq N$- All input values are integers.
翻译中…
Input
翻译中…
The input is given from Standard Input in the following format:
翻译中…
N Q
A_1 A_2 \ldots A_N
L_1 R_1
L_2 R_2
\vdots
L_Q R_Q翻译中…
Output
翻译中…
Output $Q$ lines. The $i$-th line should contain the answer to the $i$-th query.
翻译中…
样例
Input #1
5 4
2 1 3 3 1
2 4
1 4
1 5
3 3
Output #1
24
44
74
3
We explain the first query.
The value to be calculated is $\displaystyle\sum_{l = 2}^{4}\sum_{r = l}^{4}\sum_{j = l}^{r} A_j$.
- When $l = 2, r = 2$, $\displaystyle\sum_{j = l}^{r} A_j = 1$.
- When $l = 2, r = 3$, $\displaystyle\sum_{j = l}^{r} A_j = 4$.
- When $l = 2, r = 4$, $\displaystyle\sum_{j = l}^{r} A_j = 7$.
- When $l = 3, r = 3$, $\displaystyle\sum_{j = l}^{r} A_j = 3$.
- When $l = 3, r = 4$, $\displaystyle\sum_{j = l}^{r} A_j = 6$.
- When $l = 4, r = 4$, $\displaystyle\sum_{j = l}^{r} A_j = 3$.
From the above, the value to be calculated is $(1 + 4 + 7) + (3 + 6) + 3 = 24$.
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。