A1393. [COCI-2020-2021-contest5]#4 Sjeckanje
编程题
普及+/提高
知识点
题目描述
Paula likes to prepare stir fry. In order to make it as yummy as possible, she needs to chop a sequence of n integers into segments of the maximum total value.
The value of a segment is the difference of its maximum and minimum. The value of a chopped sequence is the sum of the values of the segments.
For example if we chop the sequence [1 4 1 5 3 6] into segments [1 4 1] and [5 3 6], the total value is (4 − 1) + (6 − 3) = 6.
There will be q updates of the form “add x to the elements on indices l, l + 1, . . . , r”. After each update, answer the query “What is the maximum possible value of the chopped sequence?”.
The value of a segment is the difference of its maximum and minimum. The value of a chopped sequence is the sum of the values of the segments.
For example if we chop the sequence [1 4 1 5 3 6] into segments [1 4 1] and [5 3 6], the total value is (4 − 1) + (6 − 3) = 6.
There will be q updates of the form “add x to the elements on indices l, l + 1, . . . , r”. After each update, answer the query “What is the maximum possible value of the chopped sequence?”.
输入格式
The first line contains integers n and q (1 ≤ n, q ≤ 200 000), the length of the sequence and the number of updates.
The second line contains n integers ai (−10^8 ≤ x ≤ 10^8), the sequence Paula needs to chop.
Each of the following q lines contains integers l, r (1 ≤ l ≤ r ≤ n), and x (−10^8 ≤ x ≤ 10^8), describing an update.
The second line contains n integers ai (−10^8 ≤ x ≤ 10^8), the sequence Paula needs to chop.
Each of the following q lines contains integers l, r (1 ≤ l ≤ r ≤ n), and x (−10^8 ≤ x ≤ 10^8), describing an update.
输出格式
Output q lines, the maximum possible value of the sequence after each update.
输入输出样例
输入 #1
4 3 1 2 3 4 1 2 1 1 1 2 2 3 1
输出 #1
2 2 0
说明/提示
Subtask Points Constraints
1 15 1 ≤ n, q ≤ 200
2 40 1 ≤ n, q ≤ 3000
3 55 No additional constraints.
Clarification of the first example:
Possible optimal choppings after each update are respectively: [2 3 3 4], [4 3] [3 4], and [4 4 4 4].
1 15 1 ≤ n, q ≤ 200
2 40 1 ≤ n, q ≤ 3000
3 55 No additional constraints.
Clarification of the first example:
Possible optimal choppings after each update are respectively: [2 3 3 4], [4 3] [3 4], and [4 4 4 4].