Official Editorial

For any segment $[l, r]$ with at least three elements, if there exists $i$ such that $l\le i\le i+2\le r$ and $a_i \leq a_{i+2} \leq a_{i+1}$ or $a_i \geq a_{i+2} \geq a_{i+1}$, then the segment can be split into two segments $l, l+1, \dots, i+1$ and $i+2, i+3, \dots, r$. It may be proven that the sum of the values of the two segments is at least as high as the value of the initial segment. More generally, if a segment isn't strictly increasing or strictly decreasing, we can split it into two segments without lowering the total value. Therefore, an optimal solution can be constructed with only strictly increasing or decreasing segments. This paves the way for several key properties.

Define array $D$ of length $N-1$ such that $D_i = A_{i+1} - A_i$. If the current segment $s = [l, r]$ is increasing, then $D_i > 0$ for $i \in [l, r)$ and $\sum_{i=l}^{r-1} D_i = \text {max}(s) - \text {min}(s)$. If the current segment $s = [l, r]$ is decreasing, then $D_i < 0$ for $i \in [l, r)$ and $-1 \cdot \sum_{i=l}^{r-1} D_i = \text {max}(s) - \text {min}(s)$. Between any two adjacent selected segments $[a, b]$ and $[b+1, c]$, $D_b$ must not included in our answer. With this formulation, adding integer $x$ to all elements $l, l+1, \dots, r$ is equivalent to performing the point updates $D_{l-1}\mathrel{+}=x$ and $D_{r}\mathrel{-}=x$.

Now, the problem becomes selecting segments on $D$ rather than the original $A$, where each segment contributes the absolute value of the sum of its elements to the final answer. Every two neighboring segments must be separated by at least one element (see $D_b$ above), and all elements in each segment must be either $< 0$ or $> 0$. One way to go from here is with a segment tree. Each Node stores the maximum value of its segment for each of the four cases of taking or not taking the first or last element, as well as the border elements of its segment. When merging, we must pay attention to only combine two segments together if the signs of their border elements to be combined are the same to ensure that the combined segment continues to be either strictly increasing or decreasing.

Time Complexity: $\mathcal O(N + Q\log N)$

Copy
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

 Code Snippet: Segtree Node (Click to expand)

 Code Snippet: Segtree (Click to expand)

int main() {
	ios_base::sync_with_stdio(false);