/*
Sjeckanje – COI 2021 R5
-------------------------------------------------
Maximum value after range-add updates.
Key facts
----------
* Let d[i] = a[i+1] – a[i] (1 ≤ i ≤ n-1).
* Best chopping value = Σ |d[i]| minus those |d[i]| that we
decide to “cut away”.
* Two consecutive differences of *opposite* sign may **not**
be kept simultaneously (otherwise the segment would
contain both an up-step and a down-step → not monotone).
↳ Choose a subset of indices that maximises
Σ |d[i]| subject to:
if we keep d[i] and d[i+1] then sign(d[i])·sign(d[i+1]) ≠ −1
We maintain a segment tree.
Each node keeps the best sum for the four possibilities
(keep / drop the first diff, keep / drop the last diff).
Node fields
-----------
- val[2][2] : maximum sum for
val[lf][rg] where
lf = 1 if the first diff of the segment is kept
rg = 1 if the last diff of the segment is kept
- sL, sR : sign of first / last diff in the segment
(-1, 0, +1)
Merge rule
----------
For every combination of (lf1, rg1) from left child
and (lf2, rg2) from right child:
* invalid if rg1 = 1 && lf2 = 1
&& signs are opposite (+1 vs −1)
* otherwise new-left = lf1
new-right = rg2
val = sum of the two children
Complexity
----------
Build : O(n)
Update: O(log n) (only two point updates per query)
Answer : O(1)
-------------------------------------------------
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll NEG_INF = -(1LL << 60);
struct Node {
ll val[2][2]; // val[keepLeft][keepRight]
int sL, sR; // sign of first / last diff
Node() {
for (int i = 0; i < 2; ++i)
for (int j = 0; j < 2; ++j)
val[i][j] = NEG_INF;
sL = sR = 0;
}
};
inline int sgn(ll x) { return (x > 0) - (x < 0); }
Node merge(const Node& A, const Node& B) {
if (A.val[0][0] == NEG_INF) return B;
if (B.val[0][0] == NEG_INF) return A;
Node C;
C.sL = A.sL;
C.sR = B.sR;
for (int al = 0; al <= 1; ++al)
for (int ar = 0; ar <= 1; ++ar)
if (A.val[al][ar] != NEG_INF)
for (int bl = 0; bl <= 1; ++bl)
for (int br = 0; br <= 1; ++br)
if (B.val[bl][br] != NEG_INF) {
if (ar && bl) {
// two consecutive kept diffs – must not have opposite signs
int s1 = A.sR, s2 = B.sL;
if (s1 != 0 && s2 != 0 && s1 != s2) continue;
}
ll cand = A.val[al][ar] + B.val[bl][br];
int nl = al;
int nr = br;
C.val[nl][nr] = max(C.val[nl][nr], cand);
}
return C;
}
struct SegTree {
int n; // number of diffs (n = N-1)
vector<Node> st; // 4*n
SegTree(int _n = 0) { init(_n); }
void init(int _n) {
n = _n;
st.assign(4 * max(1, n), Node());
}
Node make_leaf(ll diff) {
Node nd;
nd.sL = nd.sR = sgn(diff);
nd.val[0][0] = 0;
nd.val[1][1] = llabs(diff); // keeping the only diff
// impossible mixed states stay NEG_INF
return nd;
}
void build(int p, int l, int r, const vector<ll>& diff) {
if (l == r) {
st[p] = make_leaf(diff[l]);
return;
}
int mid = (l + r) >> 1;
build(p << 1, l, mid, diff);
build(p << 1 | 1, mid + 1, r, diff);
st[p] = merge(st[p << 1], st[p << 1 | 1]);
}
void build(const vector<ll>& diff) { // diff is 1-based of size n
if (n == 0) return;
build(1, 1, n, diff);
}
// point update: position idx gets new diff value 'val'
void update(int p, int l, int r, int idx, ll val) {
if (l == r) {
st[p] = make_leaf(val);
return;
}
int mid = (l + r) >> 1;
if (idx <= mid) update(p << 1, l, mid, idx, val);
else update(p << 1 | 1, mid + 1, r, idx, val);
st[p] = merge(st[p << 1], st[p << 1 | 1]);
}
void update(int idx, ll val) { // idx is 1-based in diff array
if (n == 0) return;
update(1, 1, n, idx, val);
}
ll best() const {
if (n == 0) return 0LL;
const Node& rt = st[1];
ll ans = 0;
for (int i = 0; i <= 1; ++i)
for (int j = 0; j <= 1; ++j)
ans = max(ans, rt.val[i][j]);
return ans;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, Q;
if (!(cin >> N >> Q)) return 0;
vector<ll> a(N + 1);
for (int i = 1; i <= N; ++i) cin >> a[i];
int M = max(0, N - 1); // number of diffs
vector<ll> diff(M + 1); // 1-based
for (int i = 1; i <= M; ++i) diff[i] = a[i + 1] - a[i];
SegTree seg(M);
if (M) seg.build(diff);
while (Q--) {
int l, r;
ll x;
cin >> l >> r >> x;
if (l > 1) {
int idx = l - 1;
diff[idx] += x; // d[l-1] increases by x
seg.update(idx, diff[idx]);
}
if (r < N) {
int idx = r;
diff[idx] -= x; // d[r] decreases by x
seg.update(idx, diff[idx]);
}
cout << seg.best() << '\n';
}
return 0;
}
