#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 2e5;
const ll INF = 1e18;
struct Query
{
int l, r, v;
};
int N, Q;
int A[MAXN+10];
Query B[MAXN+10];
int ans[MAXN+10];
struct Node
{
ll val, maxv, minv;
Node() : val(0), maxv(0), minv(0) {}
};
Node operator + (const Node &p, const Node &q)
{
Node ret;
ret.maxv=max(p.maxv, q.maxv);
ret.minv=min(p.minv, q.minv);
ret.val=max({p.val, q.val, p.maxv-q.minv, q.maxv-p.minv});
return ret;
}
struct SEG
{
Node tree[MAXN*4+10];
ll lazy[MAXN*4+10];
void busy(int node, int tl, int tr)
{
if(lazy[node]==0) return;
tree[node].maxv+=lazy[node];
tree[node].minv+=lazy[node];
if(tl!=tr)
{
lazy[node*2]+=lazy[node];
lazy[node*2+1]+=lazy[node];
}
lazy[node]=0;
return;
}
void update(int node, int tl, int tr, int l, int r, ll k)
{
busy(node, tl, tr);
if(l<=tl && tr<=r)
{
lazy[node]+=k;
busy(node, tl, tr);
return;
}
if(r<tl || tr<l) return;
int mid=tl+tr>>1;
update(node*2, tl, mid, l, r, k);
update(node*2+1, mid+1, tr, l, r, k);
tree[node]=tree[node*2]+tree[node*2+1];
}
int query(int node, int tl, int tr, ll k, Node p)
{
if(tl==tr)
{
Node t;
if(p.val<0) t=tree[node];
else t=p+tree[node];
if(t.val<=k) return tl-1;
return tl;
}
int mid=tl+tr>>1;
busy(node, tl, tr);
busy(node*2, tl, mid);
busy(node*2+1, mid+1, tr);
Node t;
if(p.val<0) t=tree[node*2+1];
else t=tree[node*2+1]+p;
if(t.val<=k) return query(node*2, tl, mid, k, t);
else return query(node*2+1, mid+1, tr, k, p);
}
ll get(int node, int tl, int tr, int p)
{
busy(node, tl, tr);
if(tl==tr) return tree[node].minv;
int mid=tl+tr>>1;
if(p<=mid) return get(node*2, tl, mid, p);
else return get(node*2+1, mid+1, tr, p);
}
Node get2(int node, int tl, int tr, int l, int r)
{
if(l<=tl && tr<=r) return tree[node];
int mid=tl+tr>>1;
if(r<=mid) return get2(node*2, tl, mid, l, r);
if(mid+1<=l) return get2(node*2+1, mid+1, tr, l, r);
return get2(node*2, tl, mid, l, mid)+get2(node*2+1, mid+1, tr, mid+1, r);
}
}seg;
ll S[MAXN+10], P[MAXN+10];
vector<int> distribute_candies(vector<int> _C, vector<int> _L, vector<int> _R, vector<int> _V)
{
N=_C.size(); Q=_L.size();
for(int i=1; i<=N; i++) A[i]=_C[i-1];
for(int i=1; i<=Q; i++) B[i]={_L[i-1]+1, _R[i-1]+1, _V[i-1]};
vector<pii> V;
for(int i=1; i<=Q; i++)
{
V.push_back({B[i].l, i});
V.push_back({B[i].r+1, -i});
}
sort(V.begin(), V.end());
ll sum=0;
for(int i=1, j=0; i<=N; i++)
{
for(; j<V.size() && V[j].first<=i; j++)
{
int t=V[j].second;
if(t>0)
{
seg.update(1, 0, Q, t, Q, B[t].v);
sum+=B[t].v;
}
else
{
seg.update(1, 0, Q, -t, Q, -B[-t].v);
sum+=-B[-t].v;
}
}
Node t;
t.val=-1;
int pos=seg.query(1, 0, Q, A[i], t);
Node node=seg.get2(1, 0, Q, pos, Q);
ll val;
if(pos==-1) val=A[i];
else val=seg.get(1, 0, Q, pos);
if(pos==-1)
{
node.maxv=max(node.maxv, (ll)A[i]);
}
if(val==node.maxv) ans[i]=sum-node.minv;
else if(val==node.minv) ans[i]=A[i]-(node.maxv-sum);
}
return vector<int>(ans+1, ans+N+1);
}
