#include <bits/stdc++.h>
#define ar array
#define fi first
#define se second
using namespace std;
typedef long double ld;
typedef long long ll;
const int inf=2e9+9;
const ll linf=4e18+18;
const int N=2e5;
struct fenw {
vector<ll> f1, f2;
int n;
fenw(int n=0): n(n) {
f1.assign(n+1,0LL), f2=f1;
}
void upd(vector<ll>&f, int p, ll x) { ++p;
for (; p<=n; p+=(p&-p)) f[p]+=x;
}
void rng_upd(int l, int r, ll x) {
upd(f1,l,x), upd(f1,r,-x);
upd(f2,l,x*l), upd(f2,r,-x*r);
}
ll sum(int p, ll ans=0) {
int p1=p;
for (; p; p-=(p&-p)) ans+=f1[p]*p1-f2[p];
return ans;
}
ll get(int p) {return sum(p+1)-sum(p);}
};
struct segtr {
struct node {
ll sum;
pair<int,bool> l, r;
node() {}
};
vector<node> t;
fenw fw;
int n;
segtr(ll *x, int n): n(n) {
fw={n};
for (int i=0; i<n; ++i) fw.rng_upd(i,i+1,x[i]);
t.resize(n*4);
}
void calc(int v, int l, int r) {
int m=(l+r)/2;
t[v].sum=t[2*v+1].sum+t[2*v+2].sum;
t[v].l=t[2*v+1].l, t[v].r=t[2*v+2].r;
ll s_2=(t[2*v+1].r.fi<m-1?fw.sum(m-2):0), s_1=fw.sum(m-1);
ll s=fw.sum(m), s1=fw.sum(m+1), s2=(t[2*v+2].l.fi>m?fw.sum(m+2):0);
ll am=s1-s, am_1=s-s_1, am1=(t[2*v+2].l.fi>m?s2-s1:am);
ll am_2=(t[2*v+1].r.fi<m-1?s_1-s_2:am_1);
ll dif=0;
if (am_1<am) {
if (t[2*v+1].r.fi!=m-1&&!t[2*v+1].r.se) dif+=am_2-am_1;
if (t[2*v+2].l.fi!=m&&!t[2*v+2].l.se) dif+=am-am1;
t[v].sum+=max(0LL,am-am_1-dif);
if ((t[2*v+1].r.fi==m-1||t[2*v+1].r.se)&&
(t[2*v+2].l.fi==m||t[2*v+2].l.se)) {
if (t[2*v+1].l.fi==m-1) t[v].l={t[2*v+2].l.fi,1};
if (t[2*v+2].r.fi==m) t[v].r={t[2*v+1].r.fi,1};
}
}
else if (am_1>am) {
if (t[2*v+1].r.fi!=m-1&&t[2*v+1].r.se) dif+=am_1-am_2;
if (t[2*v+2].l.fi!=m&&t[2*v+2].l.se) dif+=am1-am;
t[v].sum+=max(0LL,am_1-am-dif);
if ((t[2*v+1].r.fi==m-1||!t[2*v+1].r.se)&&
(t[2*v+2].l.fi==m||!t[2*v+2].l.se)) {
if (t[2*v+1].l.fi==m-1) t[v].l={t[2*v+2].l.fi,0};
if (t[2*v+2].r.fi==m) t[v].r={t[2*v+1].r.fi,0};
}
}
}
void build(int v, int l, int r) {
if (l+1==r) {
t[v].sum=0;
t[v].l=t[v].r={l,1};
}
else {
int m=(l+r)/2;
build(2*v+1,l,m);
build(2*v+2,m,r);
calc(v,l,r);
}
} void build() {build(0,0,n);}
void upd(int v, int tl, int tr, int l, int r) {
if (l>=r||(tl==l&&tr==r)) return;
int tm=(tl+tr)/2;
upd(2*v+1,tl,tm,l,min(r,tm));
upd(2*v+2,tm,tr,max(l,tm),r);
calc(v,tl,tr);
} void upd(int l, int r, ll x) {
fw.rng_upd(l,r,x);
upd(0,0,n,l,r);
}
};
int n, q;
ll a[N];
void solve() {
cin >> n >> q;
for (int i=0; i<n; ++i) cin >> a[i];
segtr tr(a,n); tr.build();
while(q--) {
int l, r, x; cin >> l >> r >> x; --l;
tr.upd(l,r,x);
cout << tr.t[0].sum << "\n";
}
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#ifdef disastah
cout << "Output\n\n";
#endif
/*#ifndef disastah
freopen("marathon.in","r",stdin);
freopen("marathon.out","w",stdout);
#endif*/
int tt=1;
// cin >> tt;
while (tt--) {
solve();
cout << "\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
