#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define node pair<ll,ll>
#define oo (ll)(1e18)
#define mod (ll)(1e9+7)
#define CJD (ll)(2e6+10)
#define FAST ios_base::sync_with_stdio(0);cin.tie(0);
struct kt
{
ll maxx=0,minn=0,ans=0;
};
kt IT[CJD*4];
ll n,q,lazy[CJD*4];
void upd(ll g,ll ls,ll rs,ll l,ll r,ll val)
{
if(lazy[g]!=0)
{
IT[g].maxx+=lazy[g];
IT[g].minn+=lazy[g];
if(ls!=rs)
{
lazy[g*2]+=lazy[g];
lazy[g*2+1]+=lazy[g];
}
lazy[g]=0;
}
if(l>rs||ls>r)return;
if(l<=ls&&rs<=r)
{
IT[g].maxx+=val;
IT[g].minn+=val;
if(ls!=rs)
{
lazy[g*2]+=val;
lazy[g*2+1]+=val;
}
return;
}
ll mid=(ls+rs)/2;
upd(g*2,ls,mid,l,r,val);
upd(g*2+1,mid+1,rs,l,r,val);
IT[g].maxx=max(IT[g*2].maxx,IT[g*2+1].maxx);
IT[g].minn=min(IT[g*2].minn,IT[g*2+1].minn);
IT[g].ans=max(IT[g*2].ans+IT[g*2+1].ans,IT[g].maxx-IT[g].minn);
}
signed main()
{
// freopen("centroid12.in","r",stdin);
// freopen("centroid12.out","w",stdout);
FAST;
cin >> n >> q;
for(ll i=1;i<=n;i++)
{
ll x;
cin >> x;
upd(1ll,1ll,n,i,i,x);
}
while(q--)
{
ll l,r,x;
cin >> l >> r >> x;
upd(1ll,1ll,n,l,r,x);
cout << IT[1].ans << "\n";
}
}
/*
4 3
1 2 3 4
1 2 1
1 1 2
2 3 1
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2648 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2648 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2648 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
