← 返回题目列表

AtCoder · awc0059_c

C. 果园收获

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

分数: 366 分

问题陈述

高桥管理着一个果园并种植了 N 果树成排。每棵树的编号为 1 to N和树 i 熊 A_i 水果。

这个果园里的树木有一个神秘的属性:无论收获多少次,其上的果实数量都不会减少。

的 树的 收获点 每棵树的 P_i 最初都是 0。当一棵树被收获一次时,该树上的果实数量就会添加到其收获点中。例如,如果一棵树承载 5 果实已收获 3 次,其收获点变为 5 \times 3 = 15.

收获季节已至,高桥将进行超期收获 M 天。

  • 当天 j,他从编号为 的每棵树上收获一次 L_j to R_j (树 L_j, L_j + 1, \ldots, R_j).

全部收获完成后,确定收获点 每棵树的 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
  • 第一行包含 N,树木的数量,以及 M,收获天数,以空格分隔。
  • 第二行包含 A_1, A_2, \ldots, A_N,每棵树上的水果数量,以空格分隔。
  • 以下 M 行给出了每天的收获范围。
  • 的 树的 (2 + j)第行包含左端点 L_j 和右端点 R_j 当天收获的树木范围 j,用空格分隔。

输出

P_1 P_2 \cdots P_N

输出收获点 每棵树的 P_1, P_2, \ldots, P_N 占一行,用空格分隔。


示例输入 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