#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
// for an incr segment it always makes sense to the max and mn and same is true for a decr segment
// 1 7 6 3
// 7 - 1 + 6 - 3 = 6 + 3
// when should we merge 2 segments
// mx1 - mn1 + mx2 - mn2 <= max(mx1, mx2) - min(mn1, mn2)
// mx1 + mx2 - max(mx1, mx2) <= mn1 + mn2 - min(mn1, mn2)
// min(mx1, mx2) <= max(mn1, mn2)
// would this lead in a cascading effect ?
// no proved.
// so for each L, R i should know the value of the last and first segments mx and mn
class Node{
public:
int cnt;
ll preMax, sufMax, preMin, sufMin, ans;
Node(ll val = 0){
preMax = sufMax = preMin = sufMin = val;
ans = 0;
cnt = 1;
}
void add(ll val){
preMax += val;
sufMax += val;
preMin += val;
sufMin += val;
}
};
const int N = 200 * 1000 + 3;
Node t[N << 2];
ll lazy[N << 2];
int a[N];
int n, Q;
void push(int rt){
lazy[rt << 1] += lazy[rt];
lazy[rt << 1 | 1] += lazy[rt];
t[rt << 1].add(lazy[rt]);
t[rt << 1 | 1].add(lazy[rt]);
lazy[rt] = 0;
}
void merge(int rt){
bool can = min(t[rt << 1].sufMax, t[rt << 1 | 1].preMax) < max(t[rt << 1].sufMin, t[rt << 1 | 1].preMin);
if(can && t[rt << 1].cnt + t[rt << 1 | 1].cnt - 1 == 1){
t[rt].ans = 0;
t[rt].cnt = 1;
t[rt].preMax = max(t[rt << 1].preMax, t[rt << 1 | 1].preMax);
t[rt].preMin = min(t[rt << 1].preMin, t[rt << 1 | 1].preMin);
t[rt].sufMax = t[rt].preMax;
t[rt].sufMin = t[rt].preMin;
} else {
t[rt].preMax = t[rt << 1].preMax;
t[rt].preMin = t[rt << 1].preMin;
t[rt].sufMax = t[rt << 1 | 1].sufMax;
t[rt].sufMin = t[rt << 1 | 1].sufMin;
t[rt].cnt = t[rt << 1].cnt + t[rt << 1 | 1].cnt - can;
if(!can){
t[rt].ans = t[rt << 1].ans + t[rt << 1 | 1].ans + (t[rt << 1].cnt > 1) * (t[rt << 1].sufMax - t[rt << 1].sufMin) + (t[rt << 1 | 1].cnt > 1)*(t[rt << 1 | 1].preMax - t[rt << 1 | 1].preMin);
} else {
t[rt].ans = t[rt << 1].ans + t[rt << 1 | 1].ans + (t[rt << 1].cnt > 1 && t[rt << 1 | 1].cnt > 1)*(max(t[rt << 1].sufMax, t[rt << 1 | 1].preMax) - min(t[rt << 1].sufMin, t[rt << 1 | 1].preMin));
}
}
}
void upd(int L, int R, int val, int rt = 1, int tl = 1, int tr = n){
if(tl > R || tr < L){ return; }
if(tl != tr && lazy[rt] != 0){ push(rt); }
if(tl >= L && tr <= R){
lazy[rt] += val;
t[rt].add(val);
} else {
int mid = tl + tr >> 1;
upd(L, R, val, rt << 1, tl, mid);
upd(L, R, val, rt << 1 | 1, mid + 1, tr);
merge(rt);
}
}
void solve(){
cin >> n >> Q;
for(int i = 1; i <= n; ++i){
cin >> a[i];
upd(i, i, a[i]);
}
while(Q--){
int L, R, x; cin >> L >> R >> x;
upd(L, R, x);
if(t[1].cnt == 1){ cout << t[1].preMax - t[1].preMin << '\n'; }
else{ cout << t[1].ans + t[1].preMax + t[1].sufMax - t[1].preMin - t[1].sufMin << '\n'; }
}
}
int main(){
// #ifndef ONLINE_JUDGE
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
// #endif
ios_base::sync_with_stdio(false); cin.tie(0);
int t = 1;
// cin >> t;
for(int i = 1; i <= t; i++){
// cout << "Case #" << i << ": ";
solve();
}
return 0;
}
Compilation message
Main.cpp: In function 'void upd(int, int, int, int, int, int)':
Main.cpp:86:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
86 | int mid = tl + tr >> 1;
| ~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
37836 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
37836 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
37836 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
