#include <bits/stdc++.h>
#define LL long long
#define int LL
#define F first
#define S second
#define FF F.F
#define FS F.S
#define SF S.F
#define SS S.S
#define all(x) (x).begin(), (x).end()
#define pii pair<int, int>
#define pb push_back
using namespace std;
const LL N=3000006, INF=1e18, P=998244353;
LL q=1, n, m, x, y, z, l, r, val, k, lazy[N], ans, o, u, Ans[N];
vector <pii> v[N], V;
string s;
pair<pair<pii,pii>,pii> T[N];
void push(int v){
T[v].FF.F+=lazy[v];
T[v].FS.F+=lazy[v];
lazy[v<<1]+=lazy[v];
lazy[v<<1|1]+=lazy[v];
lazy[v]=0;
}
void upd(int L=1, int R=n, int v=1){
if(l<R)push(v);
if(R<l || L>r)return;
if(L>=l && R<=r){
lazy[v]+=val;
if(L==R){
T[v].FF.S=T[v].FS.S=L;
T[v].FF.F+=lazy[v];
T[v].FS.F+=lazy[v];
lazy[v]=0;
}
return;
}
int mid=L+R>>1;
upd(L,mid,v<<1);
upd(mid+1,R,v<<1|1);
push(v<<1);
push(v<<1|1);
T[v]={{max(T[v<<1].FF,T[v<<1|1].FF),
min(T[v<<1].FS,T[v<<1|1].FS)},
{max(T[v<<1].FF.F-T[v<<1|1].FS.F, max(T[v<<1].SF, T[v<<1|1].SF)),
max(T[v<<1|1].FS.F-T[v<<1].FF.F, max(T[v<<1].SS, T[v<<1|1].SS))}};
}
pair<int, int> get_max(int L=1, int R=n, int v=1){
push(v);
if(R<l || L>r)return {-1,-1};
if(L>=l && R<=r)return T[v].FF;
int mid=L+R>>1;
return max(get_max(L, mid, v<<1), get_max(mid+1, R, v<<1|1));
}
pair<int, int> get_min(int L=1, int R=n, int v=1){
push(v);
if(R<l || L>r)return {INF,-1};
if(L>=l && R<=r)return T[v].FS;
int mid=L+R>>1;
return min(get_min(L, mid, v<<1), get_min(mid+1, R, v<<1|1));
}
pair<int, pii> get1(int ll, int rr, int L=1, int R=n, int v=1){
push(v);
if(R<ll||L>rr)return {-1,{-1,INF}};
if(L>=ll && R<=rr)return {T[v].SF,{T[v].FF.F,T[v].FS.F}};
int mid=L+R>>1;
l=L;r=mid+0; int mn=get_min().F;
l=mid+1;r=R; int mx=get_max().F;
auto [e1,m1]=get1(ll,rr,L,mid,1<<v);
auto [e2,m2]=get1(ll,rr,mid+1,R,1<<v|1);
return {max(m1.F-m2.S,max(e1, e2)), {max(m1.F,m2.F), min(m1.S,m2.S)}};
}
pair<int, pii> get2(int ll, int rr, int L=1, int R=n, int v=1){
push(v);
if(R<ll||L>rr)return {-1,{-1,INF}};
if(L>=ll && R<=rr)return {T[v].SS,{T[v].FF.F,T[v].FS.F}};
int mid=L+R>>1;
l=mid+1;r=R; int mn=get_min().F;
l=L;r=mid+0; int mx=get_max().F;
// cout<<endl<<l<<" "<<r<<" "<<"WAWAWA"<<mn<<" "<<mx<<endl;
auto [e1,m1]=get2(ll,rr,L,mid,1<<v);
auto [e2,m2]=get2(ll,rr,mid+1,R,1<<v|1);
return {max(m2.F-m1.S,max(e1, e2)), {max(m1.F,m2.F), min(m1.S,m2.S)}};
}
main(){ios_base::sync_with_stdio(false), cin.tie(0);
cin>>n>>q;
for (int i=1; i<=n; i++)cin>>val,l=r=i,upd();
while(q--){
o=0;
cin>>l>>r>>val;
upd();
l=1;r=n;
auto [mx,i]=get_max();
auto [mn,j]=get_min();
int e, mn1, mn2, mn3, mx1, mx2, mx3;
e=mx-mn;
// cout<<"AAA"<<e<<" "<<get1(2,3).F<<" "<<get2(2,3).F<<endl;
if(i>j)swap(i,j),o=1,swap(mx,mn);
ans=e+max(0,((o)?(get2(i+1,j-1).F):(get1(i+1,j-1).F)));
// cout<<ans<<endl;
// cout<<mx<<" "<<mn<<endl;
l=1;r=i-1; mx1=get_max().F;mn1=get_min().F;
l=i+1;r=j-1;mx2=get_max().F;mn2=get_min().F;
l=j+1;r=n; mx3=get_max().F;mn3=get_min().F;
// cout<<mx1<<" "<<mn1<<endl;
// cout<<mx2<<" "<<mn2<<endl;
// cout<<mx3<<" "<<mn3<<endl;
ans=max(ans,
max(max((mx1-mn1)+e, max(mx-mn1, mx1-mx)+max(max(mx2,mx3)-mn, mn-min(mn2, mn3))),
max(e+(mx3-mn3), max(mn-mn3, mx3-mn)+max(max(mx1,mx2)-mx, mx-min(mn1, mn2)))));
cout<<ans<<'\n';
}
}
/*
4 5
5 2 4 1
1 4 100000
1 4 100000
1 4 100000
1 4 100000
1 4 100000
*/
Compilation message
Main.cpp: In function 'void upd(long long int, long long int, long long int)':
Main.cpp:43:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
43 | int mid=L+R>>1;
| ~^~
Main.cpp: In function 'std::pair<long long int, long long int> get_max(long long int, long long int, long long int)':
Main.cpp:60:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
60 | int mid=L+R>>1;
| ~^~
Main.cpp: In function 'std::pair<long long int, long long int> get_min(long long int, long long int, long long int)':
Main.cpp:68:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
68 | int mid=L+R>>1;
| ~^~
Main.cpp: In function 'std::pair<long long int, std::pair<long long int, long long int> > get1(long long int, long long int, long long int, long long int, long long int)':
Main.cpp:76:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
76 | int mid=L+R>>1;
| ~^~
Main.cpp:79:7: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
79 | auto [e1,m1]=get1(ll,rr,L,mid,1<<v);
| ^
Main.cpp:80:7: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
80 | auto [e2,m2]=get1(ll,rr,mid+1,R,1<<v|1);
| ^
Main.cpp:77:19: warning: unused variable 'mn' [-Wunused-variable]
77 | l=L;r=mid+0; int mn=get_min().F;
| ^~
Main.cpp:78:19: warning: unused variable 'mx' [-Wunused-variable]
78 | l=mid+1;r=R; int mx=get_max().F;
| ^~
Main.cpp: In function 'std::pair<long long int, std::pair<long long int, long long int> > get2(long long int, long long int, long long int, long long int, long long int)':
Main.cpp:89:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
89 | int mid=L+R>>1;
| ~^~
Main.cpp:94:7: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
94 | auto [e1,m1]=get2(ll,rr,L,mid,1<<v);
| ^
Main.cpp:95:7: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
95 | auto [e2,m2]=get2(ll,rr,mid+1,R,1<<v|1);
| ^
Main.cpp:90:19: warning: unused variable 'mn' [-Wunused-variable]
90 | l=mid+1;r=R; int mn=get_min().F;
| ^~
Main.cpp:91:19: warning: unused variable 'mx' [-Wunused-variable]
91 | l=L;r=mid+0; int mx=get_max().F;
| ^~
Main.cpp: At global scope:
Main.cpp:100:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
100 | main(){ios_base::sync_with_stdio(false), cin.tie(0);
| ^~~~
Main.cpp: In function 'int main()':
Main.cpp:110:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
110 | auto [mx,i]=get_max();
| ^
Main.cpp:111:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
111 | auto [mn,j]=get_min();
| ^
Main.cpp:116:56: error: no matching function for call to 'max(int, long long int)'
116 | ans=e+max(0,((o)?(get2(i+1,j-1).F):(get1(i+1,j-1).F)));
| ^
In file included from /usr/include/c++/10/bits/char_traits.h:39,
from /usr/include/c++/10/ios:40,
from /usr/include/c++/10/istream:38,
from /usr/include/c++/10/sstream:38,
from /usr/include/c++/10/complex:45,
from /usr/include/c++/10/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
from Main.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
254 | max(const _Tp& __a, const _Tp& __b)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: template argument deduction/substitution failed:
Main.cpp:116:56: note: deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
116 | ans=e+max(0,((o)?(get2(i+1,j-1).F):(get1(i+1,j-1).F)));
| ^
In file included from /usr/include/c++/10/bits/char_traits.h:39,
from /usr/include/c++/10/ios:40,
from /usr/include/c++/10/istream:38,
from /usr/include/c++/10/sstream:38,
from /usr/include/c++/10/complex:45,
from /usr/include/c++/10/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
from Main.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
300 | max(const _Tp& __a, const _Tp& __b, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: template argument deduction/substitution failed:
Main.cpp:116:56: note: deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
116 | ans=e+max(0,((o)?(get2(i+1,j-1).F):(get1(i+1,j-1).F)));
| ^
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from Main.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
3480 | max(initializer_list<_Tp> __l)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: template argument deduction/substitution failed:
Main.cpp:116:56: note: mismatched types 'std::initializer_list<_Tp>' and 'int'
116 | ans=e+max(0,((o)?(get2(i+1,j-1).F):(get1(i+1,j-1).F)));
| ^
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from Main.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
3486 | max(initializer_list<_Tp> __l, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: template argument deduction/substitution failed:
Main.cpp:116:56: note: mismatched types 'std::initializer_list<_Tp>' and 'int'
116 | ans=e+max(0,((o)?(get2(i+1,j-1).F):(get1(i+1,j-1).F)));
| ^
