#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MX = 2e5 + 5;
int N, Q;
int A[MX];
struct segtree {
struct node {
ll leftMax = 0, leftMin = 0, rightMax = 0, rightMin = 0, x = 0;
bool alone = 0;
};
node t[4 * MX];
ll lazy[4 * MX];
void push(int v, int l, int r) {
if(lazy[v] == 0) return;
t[v].leftMax += lazy[v];
t[v].leftMin += lazy[v];
t[v].rightMax += lazy[v];
t[v].rightMin += lazy[v];
if(l != r) {
lazy[v * 2 + 0] += lazy[v];
lazy[v * 2 + 1] += lazy[v];
}
lazy[v] = 0;
}
node merge(int a, int b) {
// if not intersecting
node res;
if(t[a].rightMax < t[b].leftMin) {
res.x += t[a].x;
res.x += t[b].x;
res.x += t[b].leftMin - t[a].rightMax;
res.alone = t[a].alone && t[b].alone;
}
if(t[a].rightMin > t[b].leftMax) {
res.x += t[a].x;
res.x += t[b].x;
res.x += t[a].rightMin - t[b].leftMax;
res.alone = t[a].alone && t[b].alone;
}
if(t[a].rightMax < t[b].leftMin || t[a].rightMin > t[b].leftMax) {
if(t[a].alone && t[b].alone) {
res.leftMin = min(t[a].leftMin, t[b].leftMin);
res.rightMin = res.leftMin;
res.leftMax = max(t[a].leftMax, t[b].leftMax);
res.rightMax = res.leftMax;
} else if(t[a].alone) {
res.leftMin = min(t[a].leftMin, t[b].leftMin);
res.leftMax = max(t[a].leftMax, t[b].leftMax);
res.rightMin = t[b].rightMin;
res.rightMax = t[b].rightMax;
} else if(t[b].alone) {
res.leftMin = t[a].leftMin;
res.leftMax = t[a].leftMax;
res.rightMin = min(t[a].rightMin, t[b].rightMin);
res.rightMax = max(t[a].rightMax, t[b].rightMax);
} else {
res.leftMin = t[a].leftMin;
res.leftMax = t[a].leftMax;
res.rightMin = t[b].rightMin;
res.rightMax = t[b].rightMax;
}
return res;
}
// somehow intersecting
res.x += t[a].x;
res.x += t[b].x;
res.leftMin = t[a].leftMin;
res.leftMax = t[a].leftMax;
res.rightMin = t[b].rightMin;
res.rightMax = t[b].rightMax;
res.alone = t[a].alone && t[b].alone;
return res;
}
void update(int v, int l, int r, int ql, int qr, int x) {
push(v, l, r);
if(l > qr || r < ql) return;
if(ql <= l && qr >= r) {
lazy[v] += x;
push(v, l, r);
return;
}
int mid = (l + r) >> 1;
update(v * 2 + 0, l, mid + 0, ql, qr, x);
update(v * 2 + 1, mid + 1, r, ql, qr, x);
t[v] = merge(v * 2 + 0, v * 2 + 1);
}
void build(int v, int l, int r) {
if(l == r) {
t[v].x = 0;
t[v].alone = 1;
t[v].leftMin = t[v].leftMax = t[v].rightMin = t[v].rightMax = A[l];
return;
}
int mid = (l + r) >> 1;
build(v * 2 + 0, l, mid + 0);
build(v * 2 + 1, mid + 1, r);
t[v] = merge(v * 2 + 0, v * 2 + 1);
}
} st;
int main() {
cin.tie(0); ios_base::sync_with_stdio(0);
cin >> N >> Q;
for(int i = 1; i <= N; i++) cin >> A[i];
st.build(1, 1, N);
for(int i = 1; i <= Q; i++) {
int l, r, x;
cin >> l >> r >> x;
st.update(1, 1, N, l, r, x);
cout << st.t[1].x << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
39512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
39512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
39512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
