Sjeckanje
레이팅 미적용의견: 0
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?”.
Subtask 1 (15 points): \(1 \le n\), \(q \le 200\)
Subtask 2 (40 points): \(1 \le n\), \(q \le 3000\)
Subtask 3 (55 points): No additional constraints.
The first line contains integers \(n\) and \(q\) (\(1 \le n\), \(q \le 200\,000\)), the length of the sequence and the number
of updates.
The second line contains \(n\) integers \(a@@RISE_MATH_BLOCK_0@@i \le 10^{8}\)), the sequence Paula needs to chop.
Each of the following \(q\) lines contains integers \(l\), \(r\) (\(1 \le l \le r \le n\)), and \(x\) (−\(10^{8} \le x \le 10^{8}\)), describing an
update.
Output \(q\) lines, the maximum possible value of the sequence after each update.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 15점 | \(1 \le n\), \(q \le 200\) |
2 | 40점 | \(1 \le n\), \(q \le 3000\) |
3 | 55점 | No additional constraints. |
4 3
1 2 3 4
1 2 1
1 1 2
2 3 12
2
04 3
2 0 2 1
4 4 1
2 2 3
1 3 22
1
3Clarification 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].
평가 및 의견
Sjeckanje
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Sjeckanje