I am getting WA on test 28 on this problem.
My Approach
Basically, I am partitioning each segment $$$l...r$$$ into three partitions, $$$p^1, p^2, p^3$$$
Code
#include <bits/stdc++.h>
using namespace std;
#define ll long long
vector<vector<ll>> st;
int n;
void build(vector<int>& a, int v, int tl, int tr) {
if (tl == tr) {
if (a[tl] > 0)
st[v] = {0, a[tl], 0};
else
st[v] = {0, 0, a[tl]};
} else {
int tm = (tl + tr) / 2;
build(a, v * 2, tl, tm);
build(a, v * 2 + 1, tm + 1, tr);
// calculating maximum among three
st[v] = {st[v * 2][0] + st[v * 2][1] + st[v * 2][2] + st[v * 2 + 1][0],
st[2 * v + 1][1], st[2 * v + 1][2]};
if (st[v * 2][1] > st[v][1]) {
st[v] = {st[v * 2][0], st[v * 2][1],
st[v * 2][2] + st[v * 2 + 1][0] + st[2 * v + 1][1] +
st[2 * v + 1][2]};
}
if (st[v * 2][1] + st[v * 2][2] + st[v * 2 + 1][0] + st[2 * v + 1][1] >
st[v][1]) {
st[v] = {st[v * 2][0],
st[v * 2][1] + st[v * 2][2] + st[v * 2 + 1][0] +
st[2 * v + 1][1],
st[v * 2 + 1][2]};
}
}
}
void update(int v, int tl, int tr, int pos, int new_val) {
if (tl == tr) {
if (new_val > 0)
st[v] = {0, new_val, 0};
else
st[v] = {0, 0, new_val};
} else {
int tm = (tl + tr) / 2;
if (pos <= tm)
update(v * 2, tl, tm, pos, new_val);
else
update(v * 2 + 1, tm + 1, tr, pos, new_val);
// calculating maximum among three
st[v] = {st[v * 2][0] + st[v * 2][1] + st[v * 2][2] + st[v * 2 + 1][0],
st[2 * v + 1][1], st[2 * v + 1][2]};
if (st[v * 2][1] > st[v][1]) {
st[v] = {st[v * 2][0], st[v * 2][1],
st[v * 2][2] + st[v * 2 + 1][0] + st[2 * v + 1][1] +
st[2 * v + 1][2]};
}
if (st[v * 2][1] + st[v * 2][2] + st[v * 2 + 1][0] + st[2 * v + 1][1] >
st[v][1]) {
st[v] = {st[v * 2][0],
st[v * 2][1] + st[v * 2][2] + st[v * 2 + 1][0] +
st[2 * v + 1][1],
st[v * 2 + 1][2]};
}
}
}
int main() {
int m;
cin >> n >> m;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
st.resize(4 * n, vector<ll>(3));
build(a, 1, 0, n - 1);
cout << st[1][1] << endl;
while (m--) {
int i, x;
cin >> i >> x;
update(1, 0, n - 1, i, x);
cout << st[1][1] << endl;
}
}
