Sjeckanje

Editorial oficial 

Para cualquier segmento $[l, r]$ con al menos tres elementos, si existe $i$ tal que $l\le i\le i+2\le r$ y $a_i \leq a_{i+2} \leq a_{i+1}$ o $a_i \geq a_{i+2} \geq a_{i+1}$, entonces el segmento se puede partir en dos segmentos $l, l+1, \dots, i+1$ e $i+2, i+3, \dots, r$. Se puede demostrar que la suma de los valores de los dos segmentos es al menos tan alta como el valor del segmento inicial. Más en general, si un segmento no es estrictamente creciente o estrictamente decreciente, podemos partirlo en dos segmentos sin bajar el valor total. Por lo tanto, se puede construir una solución óptima solo con segmentos estrictamente crecientes o decrecientes. Esto abre el camino a varias propiedades clave.

Definamos el arreglo $D$ de longitud $N-1$ tal que $D_i = A_{i+1} - A_i$. Si el segmento actual $s = [l, r]$ es creciente, entonces $D_i > 0$ para $i \in [l, r)$ y $\sum_{i=l}^{r-1} D_i = \text {max}(s) - \text {min}(s)$. Si el segmento actual $s = [l, r]$ es decreciente, entonces $D_i < 0$ para $i \in [l, r)$ y $-1 \cdot \sum_{i=l}^{r-1} D_i = \text {max}(s) - \text {min}(s)$. Entre cualesquiera dos segmentos seleccionados adyacentes $[a, b]$ y $[b+1, c]$, $D_b$ no debe incluirse en nuestra respuesta. Con esta formulación, sumar el entero $x$ a todos los elementos $l, l+1, \dots, r$ es equivalente a realizar las actualizaciones puntuales $D_{l-1}\mathrel{+}=x$ y $D_{r}\mathrel{-}=x$.

Ahora, el problema se convierte en seleccionar segmentos sobre $D$ en lugar del $A$ original, donde cada segmento contribuye el valor absoluto de la suma de sus elementos a la respuesta final. Cada dos segmentos vecinos deben estar separados por al menos un elemento (ver $D_b$ arriba), y todos los elementos de cada segmento deben ser o bien $< 0$ o bien $> 0$. Una forma de continuar es con un árbol de segmentos. Cada nodo guarda el valor máximo de su segmento para cada uno de los cuatro casos de tomar o no tomar el primer o el último elemento, así como los elementos de borde de su segmento. Al fusionar, debemos prestar atención a combinar dos segmentos solo si los signos de sus elementos de borde a combinar son iguales para asegurar que el segmento combinado siga siendo estrictamente creciente o decreciente.

Complejidad temporal: $\mathcal O(N + Q\log N)$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
// BeginCodeSnip{Segtree Node}
struct Node {
	ll borders[2] = {};  // border values of segment
	ll dp[2][2] = {};    // take/not-take left and right border values
	Node() {}
	Node(ll v) {
		borders[0] = borders[1] = v;
		dp[0][1] = 0;
		dp[1][0] = 0;
		dp[0][0] = 0;
		dp[1][1] = abs(v);
	}
	// assume current is left
	Node comb(Node &other) {
		Node ret;
		ret.borders[0] = borders[0];
		ret.borders[1] = other.borders[1];
		// [	 ][	 ]
		// l	 mo	 r
		// m and o same -> taken segments are combined
		for (int l = 0; l < 2; l++) {
			for (int m = 0; m < 2; m++) {
				for (int o = 0; o < 2; o++) {
					for (int r = 0; r < 2; r++) {
						if (m && o) {
							// it's never optimal to take two opposite sign
							// values
							if ((borders[1] < 0) == (other.borders[0] < 0)) {
								ret.dp[l][r] =
								    max(ret.dp[l][r], dp[l][m] + other.dp[o][r]);
							}
						} else {
							ret.dp[l][r] = max(ret.dp[l][r], dp[l][m] + other.dp[o][r]);
						}
					}
				}
			}
		}
		return ret;
	}
 
	// modify a single-element Node segment by +v
	void upd(ll v) {
		borders[0] += v;
		borders[1] += v;
		dp[1][1] = abs(borders[0]);
	}
};
// EndCodeSnip
 
// BeginCodeSnip{Segtree}
struct SegTree {
	Node val;
	int gL, gR, mid;
	SegTree *left, *right;
	SegTree(int l, int r, vector<Node> &nums) {
		gL = l;
		gR = r;
		mid = (gL + gR) / 2;
		if (l == r) {
			val = nums[l];
		} else {
			left = new SegTree(l, mid, nums), right = new SegTree(mid + 1, r, nums);
			val = left->val.comb(right->val);
		}
	}
 
	void update(int idx, ll updval) {
		if (gL == gR) {
			val.upd(updval);
		} else {
			if (idx <= (gL + gR) / 2) {
				left->update(idx, updval);
			} else {
				right->update(idx, updval);
			}
			val = left->val.comb(right->val);
		}
	}
};
// EndCodeSnip
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int N, Q;
	cin >> N >> Q;
	vector<Node> D(N - 1);
	int a;
	cin >> a;
	// compute difference array
	for (int i = 0; i < N - 1; i++) {
		int b;
		cin >> b;
		D[i] = Node(b - a);
		swap(a, b);
	}
 
	// a_(i + 1) - a(i)
	SegTree sgt(0, N - 2, D);
	for (int q = 0; q < Q; q++) {
		int l;
		int r;
		ll x;
		cin >> l >> r >> x;
		l--, r--;
 
		if (l - 1 >= 0) { sgt.update(l - 1, x); }
		if (r < N - 1) { sgt.update(r, -x); }
		cout << sgt.val.dp[1][1] << '\n';
	}
}