#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const int MAX_N = 2e5 + 5;
const lint INF = 1e18;
int n, q;
array<lint, MAX_N> a;
struct Node {
lint val;
lint maxmax, maxmin, minmax, minmin;
lint l_max, l_min, r_max, r_min;
} st[4 * MAX_N];
lint lazy[4 * MAX_N];
void propogate(int u) {
if (lazy[u] == 0) return;
for (int v : {2 * u, 2 * u + 1}) {
st[v].l_max += lazy[u], st[v].r_max += lazy[u];
st[v].l_min -= lazy[u], st[v].r_min -= lazy[u];
st[v].maxmax += 2 * lazy[u], st[v].minmin -= 2 * lazy[u];
}
lazy[u] = 0;
}
Node merge(Node& x, Node& y) {
Node ans;
ans.val = max({x.val + y.val, x.r_min + y.l_max, x.r_max + y.l_min});
ans.maxmax = max({x.l_max + y.r_max, x.maxmax + y.minmax, x.maxmin + y.maxmax});
ans.maxmin = max({x.l_max + y.r_min, x.maxmax + y.minmin, x.maxmin + y.maxmin});
ans.minmax = max({x.l_min + y.r_max, x.minmax + y.minmax, x.minmin + y.maxmax});
ans.minmin = max({x.l_min + y.r_min, x.minmax + y.minmin, x.minmin + y.maxmin});
ans.l_max = max({x.l_max + y.val, x.maxmax + y.l_min, x.maxmin + y.l_max});
ans.l_min = max({x.l_min + y.val, x.minmax + y.l_min, x.minmin + y.l_max});
ans.r_max = max({x.val + y.r_max, x.r_max + y.minmax, x.r_min + y.maxmax});
ans.r_min = max({x.val + y.r_min, x.r_max + y.minmin, x.r_min + y.maxmin});
return ans;
}
void build(int u = 1, int lo = 1, int hi = n) {
if (lo == hi) {
st[u].val = 0;
st[u].l_max = st[u].r_max = a[lo];
st[u].l_min = st[u].r_min = -a[lo];
st[u].maxmax = st[u].maxmin = st[u].minmax = st[u].minmin = -INF;
return;
}
int mid = (lo + hi) / 2;
build(2 * u, lo, mid), build(2 * u + 1, mid + 1, hi);
st[u] = merge(st[2 * u], st[2 * u + 1]);
}
void update(int l, int r, lint x, int u = 1, int lo = 1, int hi = n) {
if (r < lo || hi < l) return;
if (l <= lo && hi <= r) {
st[u].l_max += x, st[u].r_max += x;
st[u].l_min -= x, st[u].r_min -= x;
st[u].maxmax += 2 * x, st[u].minmin -= 2 * x;
lazy[u] += x;
return;
}
propogate(u);
int mid = (lo + hi) / 2;
update(l, r, x, 2 * u, lo, mid), update(l, r, x, 2 * u + 1, mid + 1, hi);
st[u] = merge(st[2 * u], st[2 * u + 1]);
}
void debug(int u = 1, int lo = 1, int hi = n) {
cout << lo << " " << hi << ": " << endl;
cout << "VAL " << st[u].val << endl;
cout << "MAXMAX " << st[u].maxmax << endl;
cout << "MAXMIN " << st[u].maxmin << endl;
cout << "MINMAX " << st[u].minmax << endl;
cout << "MINMIN " << st[u].minmin << endl;
cout << "LMAX " << st[u].l_max << endl;
cout << "LMIN " << st[u].l_min << endl;
cout << "RMAX " << st[u].r_max << endl;
cout << "RMIN " << st[u].r_min << endl;
if (lo == hi) return;
int mid = (lo + hi) / 2;
debug(2 * u, lo, mid), debug(2 * u + 1, mid + 1, hi);
}
int main() {
// freopen("sje.in", "r", stdin);
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> a[i];
build();
for (int i = 1; i <= q; i++) {
int l, r; cin >> l >> r;
lint x; cin >> x;
update(l, r, x);
// if (i == q) debug();
cout << st[1].val << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
