[COCI2020-2021#5] Sjeckanje

给定一个包含 $n$ 个整数的数组 $a$。接着进行 $q$ 次修改，每次给定整数 $l,r,x$。表示将 $[l,r]$ 内的所有元素加上 $x$。 规定一个区间的权值为**该区间的最大值减去最小值**。现要将 $a$ 数组分为若干个连续的区间。规定一个已被分为若干个区间的数组的权值为**该数组所有区间的权值之和**。求数组 $a$ 在**每次修改**后的所有分法中，数组权值的最大值。

第一行输入整数 $n,q$，分别表示数组的长度和修改的次数。 第二行输入 $n$ 个整数 $a_i$。 接下来的 $q$ 行，每行输入整数 $l,r,x$，表示修改的信息。

输出 $q$ 行，其中第 $i$ 行输出数组 $a$ 在第 $i$ 次修改后的所有分法中，数组权值的最大值。

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

2
2
0

4 3
2 0 2 1
4 4 1
2 2 3
1 3 2

2
1
3

#### 样例 1 解释 |修改次数|本次修改后的数组|其中一种最优分法|数组权值| | :----------: | :----------: | :----------: | :----------: | |$1$|$[2,3,3,4]$|$[2,3,3,4]$|$2$| |$2$|$[4,3,3,4]$|$[4,3],[3,4]$|$2$| |$3$|$[4,4,4,4]$|$[4,4,4,4]$|$0$| #### 数据规模与约定 **本题采用捆绑测试**。 |Subtask|分值|数据范围及约定| | :----------: | :----------: | :----------: | |$1$|$15$|$1 \le n,q \le 200$| |$2$|$40$|$1 \le n,q \le 3000$| |$3$|$55$|无| 对于 $100\%$ 的数据，$1 \le n,q \le 2 \times 10^5$，$-10^8 \le a_i,x \le 10^8$，$1 \le l \le r \le n$。 #### 说明 **本题分值按 COCI 原题设置，满分 $110$。** **题目译自 [COCI2020-2021](https://hsin.hr/coci/) [CONTEST #5](https://hsin.hr/coci/contest5_tasks.pdf) _T5 Sjeckanje_。**