#include <bits/stdc++.h>
#define forr(_a,_b,_c) for(_a = (_b); _a <= (_c); ++_a)
#define ford(_a,_b,_c) for(_a = (_b) + 1; _a --> (_c);)
#define forf(_a,_b,_c) for(_a = (_b); _a < (_c); ++_a)
#define st first
#define nd second
#define ll long long
#define ull unsigned long long
#define pii pair <int,int>
#define pll pair <ll,ll>
#define piii pair <int,pii>
#define vi vector <int>
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define file "test"
using namespace std;
const int N = 5e5 + 5;
const ll oo = 1e16;
const ll mod = 1e9 + 7;
struct node {
ll l,r,uu,vv,uv,vu;
node operator + (node a){
node k;
k.uu = max (uu + a.uu,uv + a.vu);
k.vv = max (vu + a.uv,vv + a.vv);
k.uv = max (uu + a.uv,uv + a.vv);
k.vu = max (vu + a.uu,vv + a.vu);
if (r <= a.l){
k.uu = max (k.uu,uu + a.uu + a.l - r);
k.vv = max (k.vv,vu + a.uv + a.l - r);
k.uv = max (k.uv,uu + a.uv + a.l - r);
k.vu = max (k.vu,vu + a.uu + a.l - r);
}
else {
k.uu = max (k.uu,uv + a.vu - a.l + r);
k.vv = max (k.vv,vv + a.vv - a.l + r);
k.uv = max (k.uv,uv + a.vv - a.l + r);
k.vu = max (k.vu,vv + a.vu - a.l + r);
}
k.l = l;
k.r = a.r;
return k;
}
};
node tree[4 * N];
ll lazy[N],a[N];
void down (int i){
if (lazy[i] == 0) return;
lazy[(i << 1)] += lazy[i];
lazy[(i << 1) | 1] += lazy[i];
tree[(i << 1)].l += lazy[i];
tree[(i << 1)].r += lazy[i];
tree[(i << 1) | 1].l += lazy[i];
tree[(i << 1) | 1].r += lazy[i];
lazy[i] = 0;
}
void build (int i, int l, int r){
if (l == r){
tree[i] = {a[l],a[l],0,0,-oo,-oo};
return;
}
int mid = (l + r) >> 1;
build ((i << 1), l, mid);
build ((i << 1) | 1, mid + 1, r);
tree[i] = (tree[(i << 1)] + tree[(i << 1) | 1]);
// cout << l << " " << r << " " << tree[i].l << " " << tree[i].r << " " << tree[i].uu << " " << tree[i].vv
// << " " << tree[i].uv << " " << tree[i].vu << "\n";
}
void update (int i, int l, int r, int u, int v, ll val){
if (l > v || r < u)
return;
if (l >= u && r <= v){
tree[i].l += val;
tree[i].r += val;
lazy[i] += val;
return;
}
down(i);
int mid = (l + r) >> 1;
update((i << 1),l,mid,u,v,val);
update((i << 1) | 1, mid + 1,r,u,v,val);
tree[i] = (tree[(i << 1)] + tree[(i << 1) | 1]);
}
int n,i,q,j,k;
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> q;
forr (i,1,n)
cin >> a[i];
build(1,1,n);
// ll tmp1 = max (tree[1].uu,tree[1].vv);
// ll tmp2 = max (tree[1].uv,tree[1].vu);
// cout << max (tmp1,tmp2) << "\n";
while (q--){
cin >> i >> j >> k;
update(1,1,n,i,j,k);
ll tmp1 = max (tree[1].uu,tree[1].vv);
ll tmp2 = max (tree[1].uv,tree[1].vu);
cout << max (tmp1,tmp2) << "\n";
}
return 0;
}
/*
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
