C - 果樹園の収穫 解説 /

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

配点 : 366 点

問題文

高橋君は果樹園を経営しており、N 本の果物の木を一列に植えています。各木には番号 1 から N が付けられており、木 i には A_i 個の果物が実っています。

この果樹園の木は不思議な性質を持っており、何度収穫しても実っている果物の数は減りません。

各木の収穫ポイント P_i は初め 0 です。ある木に対して 1 回収穫を行うと、その木の収穫ポイントにその木に実っている果物の個数が加算されます。例えば、5 個の果物が実っている木に対して 3 回収穫を行うと、その木の収穫ポイントは 5 \times 3 = 15 になります。

収穫の季節になり、高橋君は M 日間かけて収穫作業を行います。

  • j 日目には、番号 L_j から R_j までのすべての木（木 L_j, L_j + 1, \ldots, R_j）に対して 1 回ずつ収穫を行います。

すべての収穫作業が終わった後、各木の収穫ポイント P_1, P_2, \ldots, P_N を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9
  • 1 \leq L_j \leq R_j \leq N
  • 入力はすべて整数
  • 答えは 64 ビット符号付き整数の範囲に収まる

入力

N M
A_1 A_2 \cdots A_N
L_1 R_1
L_2 R_2
\vdots
L_M R_M
  • 1 行目には、木の本数を表す N と、収穫作業を行う日数を表す M が、スペース区切りで与えられる。
  • 2 行目には、各木に実っている果物の個数を表す A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
  • 3 行目から M 行では、各日の収穫対象範囲が与えられる。
  • 2 + j 行目では、j 日目に収穫する木の範囲の左端 L_j と右端 R_j が、スペース区切りで与えられる。

出力

P_1 P_2 \cdots P_N

各木の収穫ポイント P_1, P_2, \ldots, P_N を、スペース区切りで 1 行に出力してください。

入力例 1

5 3
3 1 4 1 5
1 3
2 4
3 5

出力例 1

3 2 12 2 5

入力例 2

7 5
10 20 30 40 50 60 70
1 7
2 5
3 3
1 4
5 7

出力例 2

20 60 120 120 150 120 140

入力例 3

10 8
100 200 300 400 500 600 700 800 900 1000
1 5
3 8
6 10
2 4
1 10
5 5
7 9
1 3

出力例 3

300 800 1500 1600 2000 1800 2800 3200 2700 2000

Score : 366 pts

Problem Statement

Takahashi manages an orchard and has planted N fruit trees in a row. Each tree is numbered from 1 to N, and tree i bears A_i fruits.

The trees in this orchard have a mysterious property: no matter how many times they are harvested, the number of fruits on them does not decrease.

The harvest points P_i of each tree are initially 0. When a tree is harvested once, the number of fruits on that tree is added to its harvest points. For example, if a tree bearing 5 fruits is harvested 3 times, its harvest points become 5 \times 3 = 15.

The harvest season has arrived, and Takahashi will carry out harvesting over M days.

  • On day j, he harvests once from every tree numbered from L_j to R_j (trees L_j, L_j + 1, \ldots, R_j).

After all harvesting is complete, determine the harvest points P_1, P_2, \ldots, P_N of each tree.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9
  • 1 \leq L_j \leq R_j \leq N
  • All inputs are integers
  • The answers fit within the range of a 64-bit signed integer

Input

N M
A_1 A_2 \cdots A_N
L_1 R_1
L_2 R_2
\vdots
L_M R_M
  • The first line contains N, the number of trees, and M, the number of days of harvesting, separated by a space.
  • The second line contains A_1, A_2, \ldots, A_N, the number of fruits on each tree, separated by spaces.
  • The following M lines give the harvest range for each day.
  • The (2 + j)-th line contains the left endpoint L_j and right endpoint R_j of the range of trees to harvest on day j, separated by a space.

Output

P_1 P_2 \cdots P_N

Output the harvest points P_1, P_2, \ldots, P_N of each tree on a single line, separated by spaces.

Sample Input 1

5 3
3 1 4 1 5
1 3
2 4
3 5

Sample Output 1

3 2 12 2 5

Sample Input 2

7 5
10 20 30 40 50 60 70
1 7
2 5
3 3
1 4
5 7

Sample Output 2

20 60 120 120 150 120 140

Sample Input 3

10 8
100 200 300 400 500 600 700 800 900 1000
1 5
3 8
6 10
2 4
1 10
5 5
7 9
1 3

Sample Output 3

300 800 1500 1600 2000 1800 2800 3200 2700 2000