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