#include"candies.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
const long long INF=1e18;
struct query
{
int idx;
pair<long long,long long> val;
};
long long lazy[MAXN*4],fen[MAXN],cv[MAXN],sum=0;
pair<long long,long long> seg[MAXN*4];
int type[MAXN];
vector<query> vq[MAXN];
pair<long long,long long> operator+(const pair<long long,long long>& a,const pair<long long,long long>& b)
{
return {max(a.first,b.first),min(a.second,b.second)};
}
void updf(int i,int n,int val) { for(;i<=n;i+=i&-i) fen[i]+=val; }
long long getf(int i) { long long ans=0;for(;i;i-=i&-i) ans+=fen[i];return ans; }
void build(int l,int r,int pos)
{
seg[pos]={-INF,INF};
if(l==r) return ;
int mid=(l+r)/2;
build(l,mid,pos*2);
build(mid+1,r,pos*2+1);
}
void down(int pos)
{
long long val=lazy[pos];
seg[pos*2].first+=val,seg[pos*2].second+=val,lazy[pos*2]+=val;
seg[pos*2+1].first+=val,seg[pos*2+1].second+=val,lazy[pos*2+1]+=val;
lazy[pos]=0;
}
void updset(int l,int r,int i,pair<long long,long long> val,int pos)
{
if(i<l||r<i) return ;
if(l==r)
{
seg[pos]=val;
return ;
}
int mid=(l+r)/2;
down(pos);
updset(l,mid,i,val,pos*2);
updset(mid+1,r,i,val,pos*2+1);
seg[pos]=seg[pos*2]+seg[pos*2+1];
}
void update(int l,int r,int u,int v,long long val,int pos)
{
if(v<l||r<u) return ;
if(u<=l&&r<=v)
{
seg[pos]={seg[pos].first+val,seg[pos].second+val};
return ;
}
int mid=(l+r)/2;
down(pos);
update(l,mid,u,v,val,pos*2);
update(mid+1,r,u,v,val,pos*2+1);
seg[pos]=seg[pos*2]+seg[pos*2+1];
}
pair<long long,long long> getidx(int l,int r,int i,int pos)
{
if(l==r) return seg[pos];
int mid=(l+r)/2;
down(pos);
if(i<=mid) return getidx(l,mid,i,pos*2);
return getidx(mid+1,r,i,pos*2+1);
}
int walk(int l,int r,pair<long long,long long> val,long long c,int pos)
{
if(l==r) return l+1;
int mid=(l+r)/2;
down(pos);
pair<long long,long long> res=val+seg[pos*2+1];
if(res.first-res.second<=c) return walk(l,mid,res,c,pos*2);
return walk(mid+1,r,val,c,pos*2+1);
}
int walk(int n,long long c)
{
if(seg[1].first-seg[1].second<=c) return 0;
return walk(0,n,{-INF,INF},c,1);
}
void updidx(int i,int n,pair<long long,long long> val)
{
if(val.first==-INF)
{
sum-=cv[i],type[i]=0;
updf(i+1,n+1,-cv[i]);
updset(0,n,i,val,1);
update(0,n,i,n,cv[i],1);
}
else
{
if(val.first>=0) type[i]=1;
else type[i]=-1;
sum+=(cv[i]=val.first);
updf(i+1,n+1,cv[i]);
updset(0,n,i,{0,0},1);
update(0,n,i,i,-getf(i+1),1);
update(0,n,i+1,n,-cv[i],1);
}
}
vector<int> distribute_candies(vector<int> c,vector<int> l,vector<int> r,vector<int> v)
{
int n=c.size(),q=l.size();
vector<int> ans;
for(int i=0;i<q;i++)
{
vq[l[i]].push_back({i+1,{v[i],v[i]}});
vq[r[i]+1].push_back({i+1,{-INF,INF}});
}
build(0,q,1);
for(int i=0;i<n;i++)
{
updidx(0,q,{0,-c[i]});
for(auto v:vq[i]) updidx(v.idx,q,v.val);
int pos=walk(q,c[i]);
pair<long long,long long> curr=getidx(0,q,pos,1);
if(type[pos]!=1) ans.push_back(curr.first+sum);
else ans.push_back(curr.second+sum+c[i]);
}
return ans;
}
