#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define IOS ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define F first
#define S second
#define sz(x) x.size()
#define all(x) x.begin(), x.end()
#define pb push_back
const int Inf = 2e9 + 10;
const int Mod = 1e9 + 7;
const int LG = 25;
const int SQ = 400;
const int Alpha = 27;
const int maxN = 2e5 + 10;
ll n, q;
ll a[maxN];
struct SegTree {
struct Node {
ll ans;
ll L1;
ll L2;
ll R1;
ll R2;
ll lazy;
Node() {
ans = L1 = L2 = R1 = R2 = lazy = 0;
}
} t[maxN<<2];
Node merge(Node lc, Node rc, ll L, ll R) {
Node ret;
if(L+2 == R) {
ret.ans = abs(lc.R1 - rc.L1);
ret.L1 = lc.L1;
ret.L2 = rc.L1;
ret.R1 = rc.R1;
ret.R2 = lc.R1;
return ret;
}
if(L+3 == R) {
ret.L1 = lc.L1;
ret.L2 = rc.L1;
ret.R1 = rc.R1;
ret.R2 = rc.R2;
ll x = lc.R1;
ll y = rc.L1;
ll z = rc.L2;
if(x <= y and y <= z) {
ret.ans = z-x;
}
else if(x <= y and y >= z) {
ret.ans = max(y-x, y-z);
}
else if(x >= y and y <= z) {
ret.ans = max(x-y, z-y);
}
else if(x >= y and y >= z) {
ret.ans = x-z;
}
return ret;
}
ret.L1 = lc.L1;
ret.L2 = lc.L2;
ret.R1 = rc.R1;
ret.R2 = rc.R2;
ll mid = (L+R)>>1;
ll x = lc.R2;
ll y = lc.R1;
ll z = rc.L1;
ll w = rc.L2;
if(x <= y and y <= z and z <= w) {
ret.ans = lc.ans + rc.ans + (z-y);
}
else if(x <= y and y <= z and z >= w) {
ret.ans = lc.ans + rc.ans;
if(z-y > z-w) {
ret.ans += (z-y) - (z-w);
}
}
else if(x <= y and y >= z and z <= w) {
ret.ans = lc.ans + rc.ans;
ret.ans += max(0LL, (y-z)-(y-x)-(w-z));
}
else if(x <= y and y >= z and z >= w) {
ret.ans = lc.ans + rc.ans;
if(y-z > y-x) {
ret.ans += (y-z) - (y-x);
}
}
else if(x >= y and y <= z and z <= w) {
ret.ans = lc.ans + rc.ans;
ret.ans += max(0LL, (z-y) - (x-y) - (z-w));
}
else if(x >= y and y <= z and z >= w) {
ret.ans = lc.ans + rc.ans;
ret.ans += max(0LL, (z-y) - (x-y));
}
else if(x >= y and y >= z and z <= w) {
ret.ans = lc.ans + rc.ans;
ret.ans += max(0LL, (y-z) - (x-y) - (w-z));
}
else if(x >= y and y >= z and z >= w) {
ret.ans = lc.ans + rc.ans + y-z;
}
return ret;
}
void spread(ll id, ll L, ll R) {
ll mid = (L+R)>>1;
t[2*id+0].lazy += t[id].lazy;
t[2*id+0].L1 += t[id].lazy;
t[2*id+0].R1 += t[id].lazy;
if(mid-L > 1) {
t[2*id+0].L2 += t[id].lazy;
t[2*id+0].R2 += t[id].lazy;
}
t[2*id+1].lazy += t[id].lazy;
t[2*id+1].L1 += t[id].lazy;
t[2*id+1].R1 += t[id].lazy;
if(R-mid > 1) {
t[2*id+1].L2 += t[id].lazy;
t[2*id+1].R2 += t[id].lazy;
}
t[id].lazy = 0;
}
void initialize(ll id, ll L, ll R) {
if(L+1 == R) {
t[id].ans = 0;
t[id].L1 = a[L];
t[id].R1 = a[L];
return;
}
ll mid = (L+R)>>1;
initialize(2*id+0, L, mid);
initialize(2*id+1, mid, R);
t[id] = merge(t[2*id+0], t[2*id+1], L, R);
}
void update(ll id, ll L, ll R, ll l, ll r, ll x) {
spread(id, L, R);
if(L == l and R == r) {
t[id].lazy += x;
t[id].L1 += x;
t[id].R1 += x;
if(R-L > 1) {
t[id].L2 += x;
t[id].R2 += x;
}
return;
}
ll mid = (L+R)>>1;
if(l < mid)
update(2*id+0, L, mid, l, min(mid, r), x);
if(r > mid)
update(2*id+1, mid, R, max(l, mid), r, x);
t[id] = merge(t[2*id+0], t[2*id+1], L, R);
}
Node Get(ll id, ll L, ll R, ll l, ll r) {
spread(id, L, R);
if(L == l and R == r)
return t[id];
ll mid = (L+R)>>1;
Node lc, rc;
if(l < mid and r <= mid) {
return Get(2*id+0, L, mid, l, r);
}
if(l < mid and r > mid) {
lc = Get(2*id+0, L, mid, l, mid);
rc = Get(2*id+1, mid, R, mid, r);
return merge(lc, rc, l, r);
}
if(l >= mid and r > mid) {
return Get(2*id+1, mid, R, l, r);
}
return lc;
}
};
int main() {
IOS;
cin >> n >> q;
for(ll i = 1; i <= n; i++) {
cin >> a[i];
}
SegTree s;
s.initialize(1, 1, n+1);
while(q--) {
ll l, r, v;
cin >> l >> r >> v;
s.update(1, 1, n+1, l, r+1, v);
SegTree::Node g = s.Get(1, 1, n+1, 1, n+1);
cout << g.ans << "\n";
}
}
Compilation message
Main.cpp: In member function 'SegTree::Node SegTree::merge(SegTree::Node, SegTree::Node, ll, ll)':
Main.cpp:83:6: warning: unused variable 'mid' [-Wunused-variable]
83 | ll mid = (L+R)>>1;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
37980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
37980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
37980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
