← 返回题目列表

AtCoder · typical90_bl

064. 提升(★3)

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

配点: 3 点

問題文

日本被划分为 N 个区块,从西向东第 i 个区块(以下称为区块 i )的海拔为 A_i 。

从现在开始 Q 次地壳变化将会发生。i 在第几次地壳变化中,区块 L_i, L_i+1, \cdots, R_i 的海拔会变化 V_i 。(当V_i \geq 0 时海拔上升 |V_i| ,V_i < 0 时海拔上升 |V_i| 时下降)

那么,区块 1 减去 N 时的不便定义如下。

区画 i 的海拔高度 表示为 E_i 的情况下,不便之处是 |E_1 - E_2| + |E_2 - E_3| + \cdots + |E_{N-1} - E_N|

各地壳变动后的不便请分别求出。

制約

  • 1 \leq N, Q \leq 10^{5}
  • -10^{9} \leq A_i, V_i \leq 10^{9}
  • 1 \leq L_i \leq R_i \leq N
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

N Q
A_1 A_2 \cdots A_N
L_1 R_1 V_1
L_2 R_2 V_2
\vdots
L_Q R_Q V_Q

出力

Q 行。 列出
i 行中,i 请输出第几次地壳变动结束后的不便之处。


入力例 1

3 3
1 2 3
2 3 1
1 2 -1
1 3 2

出力例 1

3
4
4

1 次地壳变动后的各区块海拔,从西向东分别为 1, 3, 4 ,不便之处是有 |1 - 3| + |3 - 4| = 3 。
2 次地壳变动后的各区块海拔,从西向东分别为 0, 2, 4 ,不便之处是有 |0 - 2| + |2 - 4| = 4 。
3 次地壳变动后的各区块海拔,从西向东分别为 2, 4, 6 ,不便之处是有 |2 - 4| + |4 - 6| = 4 。


入力例 2

20 10
61 51 92 -100 -89 -65 -89 -64 -74 7 87 -2 51 -39 -50 63 -23 36 74 37
2 2 -45
6 19 82
2 9 36
7 13 71
16 20 90
18 20 -24
14 17 -78
10 11 -55
7 19 -26
20 20 -7

出力例 2

1164
1328
1256
1350
1440
1416
1572
1482
1430
1437