P7402 [COCI 2020/2021 #5] Sjeckanje

You are given an array $a$ containing $n$ integers. Then there are $q$ updates. Each update gives integers $l, r, x$, meaning to add $x$ to all elements in $[l, r]$. Define the weight of an interval as **the maximum value in the interval minus the minimum value in the interval**. Now you need to split array $a$ into several consecutive intervals. Define the weight of an array that has been split into several intervals as **the sum of the weights of all its intervals**. For **each update**, find the maximum possible array weight among all ways to split the array after that update.

The first line contains integers $n, q$, representing the length of the array and the number of updates. The second line contains $n$ integers $a_i$. The next $q$ lines each contain integers $l, r, x$, describing an update.

Output $q$ lines. On the $i$-th line, output the maximum possible array weight among all splits of array $a$ after the $i$-th update.

#### Explanation of Sample 1 |Number of updates|Array after this update|One optimal split|Array weight| | :----------: | :----------: | :----------: | :----------: | |$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$| #### Constraints and Notes **This problem uses bundled testdata**. |Subtask|Points|Constraints and notes| | :----------: | :----------: | :----------: | |$1$|$15$|$1 \le n, q \le 200$| |$2$|$40$|$1 \le n, q \le 3000$| |$3$|$55$|None| For $100\%$ of the testdata, $1 \le n, q \le 2 \times 10^5$, $-10^8 \le a_i, x \le 10^8$, and $1 \le l \le r \le n$. #### Additional Notes **The scoring follows the original COCI problem settings, with a full score of $110$.** **Translated from [COCI2020-2021](https://hsin.hr/coci/) [CONTEST #5](https://hsin.hr/coci/contest5_tasks.pdf) _T5 Sjeckanje_.** Translated by ChatGPT 5