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