#include <bits/stdc++.h>
#define pb push_back
#define ff first
#define ss second
#define ll long long
#define N 200005
#define INF 1000000000
#define MOD 998244353
using namespace std;
ll m[4 * N], lazy[8 * N];
ll n, q;
ll a[N], b[N];
struct block{
ll L, R, sum;
};
block node[4 * N];
void push(ll id){
m[id] += lazy[id];
lazy[id * 2] += lazy[id];
lazy[id * 2 + 1] += lazy[id];
lazy[id] = 0;
}
void lol(ll id, ll l, ll r){
if(l == r){
m[id] = a[l];
return;
}
ll mm = l + r >> 1;
lol(id * 2, l, mm);
lol(id * 2 + 1, mm + 1, r);
m[id] = max(m[id * 2], m[id * 2 + 1]);
}
void update(ll id, ll l, ll r, ll L, ll R, ll val){
push(id);
if(r < L || R < l) return;
if(L <= l && r <= R){
m[id] += val;
lazy[id * 2] += val;
lazy[id * 2 + 1] += val;
return;
}
int mm = l + r >> 1;
update(id * 2, l, mm, L, R, val);
update(id * 2 + 1, mm + 1, r, L, R, val);
m[id] = max(m[id * 2], m[id * 2 + 1]);
}
ll query(ll id, ll l, ll r, ll pos){
push(id);
if(l == r){
return m[id];
}
int mm = l + r >> 1;
if(pos <= mm) return query(id * 2, l, mm, pos);
else return query(id * 2 + 1, mm + 1, r, pos);
}
void build(ll id, ll l, ll r){
if(l > r) return;
if(l == r){
if(b[l] == 0){
node[id].L = -1;
node[id].R = -1;
}
else{
node[id].L = l;
node[id].R = r;
}
node[id].sum = 0;
return;
}
ll m = l + r >> 1;
build(id * 2, l, m);
build(id * 2 + 1, m + 1, r);
if(node[id * 2].R == -1 && node[id * 2 + 1].L == -1){
node[id].L = -1;
node[id].R = -1;
node[id].sum = 0;
}
else{
if(node[id * 2].R == -1){
node[id].L = node[id * 2 + 1].L;
node[id].R = node[id * 2 + 1].R;
node[id].sum = node[id * 2 + 1].sum;
}
else{
if(node[id * 2 + 1].L == -1){
node[id].L = node[id * 2].L;
node[id].R = node[id * 2].R;
node[id].sum = node[id * 2].sum;
}
else{
node[id].sum = node[id * 2].sum + node[id * 2 + 1].sum;
node[id].L = node[id * 2].L;
node[id].R = node[id * 2 + 1].R;
bool flag = 0;
if(b[m] == 0 || b[m + 1] == 0) flag = 1;
ll k = query(1, 1, n, node[id * 2].R);
if(b[node[id * 2].R] > 0 && b[node[id * 2 + 1].L] < 0){
node[id].sum += (2 * k - (flag ? 0 : min(abs(b[node[id * 2].R]), abs(b[node[id * 2 + 1].L]))));
}
if(b[node[id * 2].R] < 0 && b[node[id * 2 + 1].L] > 0){
node[id].sum -= (2 * k + (flag ? 0 : min(abs(b[node[id * 2].R]), abs(b[node[id * 2 + 1].L]))));
}
}
}
}
}
void prob(ll id, ll l, ll r, ll pos){
if(l > r) return;
if(l == r){
if(b[l] == 0){
node[id].L = -1;
node[id].R = -1;
}
else{
node[id].L = l;
node[id].R = r;
}
node[id].sum = 0;
return;
}
ll m = l + r >> 1;
if(m >= pos) prob(id * 2, l, m, pos);
else prob(id * 2 + 1, m + 1, r, pos);
if(node[id * 2].R == -1 && node[id * 2 + 1].L == -1){
node[id].L = -1;
node[id].R = -1;
node[id].sum = 0;
}
else{
if(node[id * 2].R == -1){
node[id].L = node[id * 2 + 1].L;
node[id].R = node[id * 2 + 1].R;
node[id].sum = node[id * 2 + 1].sum;
}
else{
if(node[id * 2 + 1].L == -1){
node[id].L = node[id * 2].L;
node[id].R = node[id * 2].R;
node[id].sum = node[id * 2].sum;
}
else{
node[id].sum = node[id * 2].sum + node[id * 2 + 1].sum;
node[id].L = node[id * 2].L;
node[id].R = node[id * 2 + 1].R;
bool flag = 0;
if(b[m] == 0 || b[m + 1] == 0) flag = 1;
ll k = query(1, 1, n, node[id * 2].R);
if(b[node[id * 2].R] > 0 && b[node[id * 2 + 1].L] < 0){
node[id].sum += (2 * k - (flag ? 0 : min(abs(b[node[id * 2].R]), abs(b[node[id * 2 + 1].L]))));
}
if(b[node[id * 2].R] < 0 && b[node[id * 2 + 1].L] > 0){
node[id].sum -= (2 * k + (flag ? 0 : min(abs(b[node[id * 2].R]), abs(b[node[id * 2 + 1].L]))));
}
}
}
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> q;
for(int i = 1; i <= n; i++){
cin >> a[i];
if(i > 1) b[i] = a[i] - a[i - 1];
}
lol(1, 1, n);
build(1, 2, n);
while(q--){
int l, r, x;
cin >> l >> r >> x;
update(1, 1, n, l, r, x);
b[l] += x;
prob(1, 2, n, l);
b[r + 1] -= x;
prob(1, 2, n, r + 1);
ll ans = node[1].sum;
x = node[1].L;
ll y = node[1].R;
if(x == -1){
cout << 0 << '\n';
}
else{
if(b[x] < 0){
ll p = query(1, 1, n, x);
ans += (p - b[x]);
}
else{
ll p = query(1, 1, n, x);
ans -= (p - b[x]);
}
if(b[y] < 0){
ll p = query(1, 1, n, y);
ans -= p;
}
else{
ll p = query(1, 1, n, y);
ans += p;
}
cout << ans << '\n';
}
}
}
Compilation message
Main.cpp: In function 'void lol(long long int, long long int, long long int)':
Main.cpp:29:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
29 | ll mm = l + r >> 1;
| ~~^~~
Main.cpp: In function 'void update(long long int, long long int, long long int, long long int, long long int, long long int)':
Main.cpp:43:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
43 | int mm = l + r >> 1;
| ~~^~~
Main.cpp: In function 'long long int query(long long int, long long int, long long int, long long int)':
Main.cpp:53:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
53 | int mm = l + r >> 1;
| ~~^~~
Main.cpp: In function 'void build(long long int, long long int, long long int)':
Main.cpp:71:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
71 | ll m = l + r >> 1;
| ~~^~~
Main.cpp: In function 'void prob(long long int, long long int, long long int, long long int)':
Main.cpp:122:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
122 | ll m = l + r >> 1;
| ~~^~~
| # |
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 |
- |
