(cache)E - Sum of Subarrays

コンテスト時間: 2025-09-14(日) 21:00 ~ 2025-09-14(日) 22:40 (100分) AtCoderホームへ戻る

E - Sum of Subarrays 解説

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : $475$ 点

問題文

長さ $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$ の値を答えとして求めてください。

制約

$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$ 番目のクエリに対する答えを出力せよ。

入力例 1Copy

Copy

出力例 1Copy

Copy

$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$ です。

Score : $475$ points

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.

Sample Input 1Copy

Copy

Sample Output 1Copy

Copy

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$ .