#include <bits/stdc++.h>
#include <atcoder/segtree>
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define crep(i,x,n) for(int i=x;i<n;i++)
#define drep(i,n) for(int i=n-1;i>=0;i--)
#define vec(...) vector<__VA_ARGS__>
#define _3cSpNGp ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
typedef long double ld;
using pii=pair<int,int>;
using vi=vector<int>;
const ll inf=1e12;
struct node{
ll val[2][2];
ll back;
void init(ll _back){
back=_back;
val[0][0]=val[1][1]=0;
val[0][1]=val[1][0]=-inf;
}
};
node _e;
node op(node l,node r){
node now;
now.init(r.back);
rep(tl,2)rep(tr,2){
ll merged=0,additional=0;
additional=max(0ll,l.back);
merged=l.val[tl][0]+r.val[0][tr]+additional; // both positive
now.val[tl][tr]=max(now.val[tl][tr],merged);
if(l.back!=-inf){
additional=max(0ll,-l.back);
}
merged=l.val[tl][1]+r.val[1][tr]+additional; // both negative
now.val[tl][tr]=max(now.val[tl][tr],merged);
merged=l.val[tl][0]+r.val[1][tr];
now.val[tl][tr]=max(now.val[tl][tr],merged);
merged=l.val[tl][1]+r.val[0][tr];
now.val[tl][tr]=max(now.val[tl][tr],merged);
}
return now;
}
node e(){
return _e;
}
int main(){
_3cSpNGp;
_e.init(0);
int n;
cin>>n;
int q;
cin>>q;
vi a(n);
rep(i,n){
cin>>a[i];
}
atcoder::segtree<node,op,e> seg(n-1);
vec(ll) d;
rep(i,n-1){
node now;
d.pb((ll)a[i+1]-a[i]);
now.init(d.back());
seg.set(i,now);
}
auto f_all=[&](int l,int r)->ll{
node now=seg.prod(l,r);
ll ans=-inf;
rep(t,2)rep(t1,2){
ans=max(ans,now.val[t][t1]);
}
return ans;
};
rep(_,q){
int l,r;
ll x;
cin>>l>>r>>x;
l--,r--;
if(l) d[l-1]+=x;
if(r!=n-1) d[r]-=x;
node now;
if(l){
now.init(d[l-1]);
seg.set(l-1,now);
}
if(r!=n-1){
now.init(d[r]);
seg.set(r,now);
}
ll ans=f_all(0,n-1);
cout<<ans<<"\n";
}
//
return 0;
}
Compilation message
Main.cpp:2:10: fatal error: atcoder/segtree: No such file or directory
2 | #include <atcoder/segtree>
| ^~~~~~~~~~~~~~~~~
compilation terminated.
