← 返回题目列表

AtCoder · awc0093_c

C. 给花坛浇水

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

分数: 366 分

问题陈述

高桥被任命负责管理花园里的花坛。

花坛包括 N 部分排列成行,编号部分 1,部分 2,……,部分 N 从左到右。最初,截面中的土壤 i 包含 A_i 升水分。

高桥将表演 M 操作按顺序进行。在 j第一次操作 (1 \leq j \leq M),对于该部分的连续范围内的每个部分 L_j 至部分 R_j,他通过以下方式改变了湿度水平 D_j 升。也就是说,他补充说 D_j 到每个此类部分的湿度水平(正 D_j 表示浇水,负数 D_j 表示排水)。

保证在任何时间点,每个部分的湿度水平在 0 和 10^{18},包括在内。

所有操作完成后,确定各部分的湿度水平。

约束

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq 2 \times 10^5
  • 0 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq L_j \leq R_j \leq N (1 \leq j \leq M)
  • -10^9 \leq D_j \leq 10^9 (1 \leq j \leq M)
  • 在任何时间点,每个部分的湿度水平介于 0 和 10^{18},包含在内
  • 所有输入值均为整数

输入

N M
A_1 A_2 \ldots A_N
L_1 R_1 D_1
L_2 R_2 D_2
\vdots
L_M R_M D_M
  • 第一行包含一个整数 N 表示节数和整数 M 代表操作次数,以空格分隔。
  • 第二行包含整数 A_1, A_2, \ldots, A_N 代表每个部分的初始湿度水平,以空格分隔。
  • 以下 M 行描述了每个操作。
  • 的 j- 这些行( (2 + j)-整个输入的第行)包含左端点 L_j,右端点 R_j,以及水分变化量 D_j 为 j第一个操作,以空格分隔。

输出

打印切片的水分含量 1 通过 N 所有操作完成后,以空格分隔的整数形式显示在一行上。


示例输入 1

5 3
10 5 8 3 6
1 3 2
2 5 -1
4 4 5

示例输出 1

12 6 9 7 5

示例输入 2

8 5
100 200 300 400 500 600 700 800
1 8 -50
3 6 100
1 4 -30
5 8 200
2 7 10

示例输出 2

20 130 330 430 760 860 860 950

示例输入 3

10 8
1000000000 500000000 0 300000000 700000000 100000000 999999999 250000000 800000000 450000000
1 10 1000000000
3 7 -500000000
1 5 200000000
6 10 300000000
2 4 -100000000
8 10 -200000000
1 1 500000000
5 9 100000000

示例输出 3

2700000000 1600000000 600000000 900000000 1500000000 1000000000 1899999999 1450000000 2000000000 1550000000