#include <bits/stdc++.h>
using namespace std;
#define int long long
inline void setmax(long long &a, long long b) {
a = max(a, b);
}
constexpr int N = 2e5 + 10;
struct Node {
long long dp[3][3], lz; //0: negative 2: positive
inline void apply(long long x) {
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
dp[i][j] += x * (i - 1 + j - 1);
}
}
lz += x;
}
};
Node t[N << 2];
int n, q, a[N];
inline void push(int c, int l, int r) {
if (t[c].lz != 0) {
t[l].apply(t[c].lz);
t[r].apply(t[c].lz);
t[c].lz = 0;
}
}
inline void pull(int c, int l, int r) {
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
t[c].dp[i][j] = -1e18;
setmax(t[c].dp[i][j], t[l].dp[i][1] + t[r].dp[1][j]);
setmax(t[c].dp[i][j], t[l].dp[i][0] + t[r].dp[2][j]);
setmax(t[c].dp[i][j], t[l].dp[i][2] + t[r].dp[0][j]);
setmax(t[c].dp[i][j], t[l].dp[i][j] + t[r].dp[1][1]);
setmax(t[c].dp[i][j], t[l].dp[1][1] + t[r].dp[i][j]);
}
}
}
void build(int c, int b, int e) {
if (e - b == 1) {
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
t[c].dp[i][j] = -1e18;
}
}
t[c].dp[1][1] = 0;
t[c].dp[1][2] = t[c].dp[2][1] = a[b];
t[c].dp[1][0] = t[c].dp[0][1] = -a[b];
return;
}
int m = (b + e) >> 1, l = c << 1, r = l | 1;
build(l, b, m);
build(r, m, e);
pull(c, l, r);
}
void update(int c, int b, int e, int u, int v, long long x) {
if (e <= u || v <= b) {
return;
}
if (u <= b && e <= v) {
t[c].apply(x);
return;
}
int m = (b + e) >> 1, l = c << 1, r = l | 1;
push(c, l, r);
update(l, b, m, u, v, x);
update(r, m, e, u, v, x);
pull(c, l, r);
}
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> q;
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
build(1, 0, n);
while (q--) {
int l, r, x;
cin >> l >> r >> x;
--l;
update(1, 0, n, l, r, x);
assert(t[1].dp[1][1] >= 0);
cout << t[1].dp[1][1] << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
