#include "bits/stdc++.h"
using namespace std;
#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif
struct SegTree {
struct node {
long long lm, rm;
long long a[2][2] = {};
};
int n;
vector<node> seg;
SegTree(const vector<long long>& v) {
n = (int) v.size();
seg.resize(2 * n - 1);
build(0, 0, n - 1, v);
}
node merge(const node& lc, const node& rc) {
node ret;
ret.lm = lc.lm;
ret.rm = lc.rm;
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < 2; ++j) {
for (int k = 0; k < 2; ++k) {
for (int l = 0; l < 2; ++l) {
if (k != l || (lc.rm >= 0 && rc.lm >= 0) || (lc.rm <= 0 && rc.rm <= 0)) {
ret.a[i][j] = max(ret.a[i][j], lc.a[i][k] + rc.a[l][j]);
}
}
}
}
}
return ret;
}
void build(int nd, int l, int r, const vector<long long>& v) {
if (l == r) {
seg[nd].lm = seg[nd].rm = v[l];
seg[nd].a[1][1] = abs(v[l]);
return;
}
int mid = (l + r) >> 1;
int rs = nd + ((mid - l + 1) << 1);
build(nd + 1, l, mid, v);
build(rs, mid + 1, r, v);
seg[nd] = merge(seg[nd + 1], seg[rs]);
}
void upd(int nd, int l, int r, int p, int v) {
if (l == r) {
seg[nd].lm = seg[nd].rm = v;
seg[nd].a[1][1] = abs(v);
return;
}
int mid = (l + r) >> 1;
int rs = nd + ((mid - l + 1) << 1);
if (p <= mid) {
upd(nd + 1, l, mid, p, v);
} else {
upd(rs, mid + 1, r, p, v);
}
seg[nd] = merge(seg[nd + 1], seg[rs]);
}
void upd(int p, int v) {
upd(0, 0, n - 1, p, v);
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
vector<long long> d(n - 1);
for (int i = 0; i < n - 1; ++i) {
d[i] = a[i + 1] - a[i];
}
SegTree st(d);
while (q--) {
int l, r, v;
cin >> l >> r >> v;
--l, --r;
if (l > 0) {
d[l - 1] += v;
st.upd(l - 1, d[l - 1]);
}
if (r < n - 1) {
d[r] -= v;
st.upd(r, d[r]);
}
long long ans = 0;
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < 2; ++j) {
ans = max(ans, st.seg[0].a[i][j]);
}
}
cout << ans << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
