#include <bits/stdc++.h>
#include "candies.h"
using namespace std;
typedef long long ll;
const ll inf=(1ll<<60);
struct obj
{
ll sum;
ll mn;
ll mn_idx;
ll mx;
ll mx_idx;
obj(){sum=0;mn=inf;mx=-inf;mn_idx=mx_idx=-3;}
obj(ll x,int idx=-3){sum=mn=mx=x;mn_idx=mx_idx=idx;}
};
obj tmerge(obj a,obj b)
{
obj r=a;
r.sum+=b.sum;
if(a.sum+b.mn<r.mn)
{
r.mn=a.sum+b.mn;
r.mn_idx=b.mn_idx;
}
if(a.sum+b.mx>r.mx)
{
r.mx=a.sum+b.mx;
r.mx_idx=b.mx_idx;
}
return r;
}
const int N=200005;
int n,q;
vector<ll> c(N);
vector<ll> mv(N);
vector<int> queries[4*N];
vector<obj> tree(4*N);
vector<ll> res(N);
int mid(int l,int r){return (l+r)/2-((l+r)<0&&((l+r)&1));}
void add_query(int idx,int l,int r,int ql,int qr,int x)
{
if(ql>qr) return;
if(l==ql&&r==qr) queries[idx].push_back(x);
else
{
int m=mid(l,r);
add_query(2*idx,l,m,ql,min(qr,m),x);
add_query(2*idx+1,m+1,r,max(ql,m+1),qr,x);
}
}
void update(int idx,int l,int r,int pos,obj o)
{
if(l==r) tree[idx]=o;
else
{
int m=mid(l,r);
if(pos<=m) update(2*idx,l,m,pos,o);
else update(2*idx+1,m+1,r,pos,o);
tree[idx]=tmerge(tree[2*idx],tree[2*idx+1]);
}
}
bool ok(obj o,ll val){return (o.mx-o.mn)>=val;}
obj descend(int idx,int l,int r,ll val,obj req=obj())
{
if(l==r) return tmerge(tree[idx],req);
int m=mid(l,r);
if(ok(tmerge(tree[2*idx+1],req),val)==1) return descend(2*idx+1,m+1,r,val,req);
else return descend(2*idx,l,m,val,tmerge(tree[2*idx+1],req));
}
ll query(int idx,int l,int r,int ql,int qr)
{
if(ql>qr) return 0;
if(l==ql&&r==qr) return tree[idx].sum;
int m=mid(l,r);
return query(2*idx,l,m,ql,min(qr,m))+query(2*idx+1,m+1,r,max(ql,m+1),qr);
}
void solve(int idx,int l,int r)
{
for(int x:queries[idx]) update(1,-2,q-1,x,obj(mv[x],x));
if(l==r)
{
obj o=descend(1,-2,q-1,c[l]);
// cout << "sums: ";
// for(int i=-2;i<=q-1;i++) cout << "[" << i << "," << query(1,-2,q-1,i,i) << "] ";
// cout << endl;
// cout << "solving " << l << ": " << o.sum << " mn[" << o.mn << "," << o.mn_idx << "] mx[" << o.mx << "," << o.mx_idx << "]" << endl;
if(o.mn_idx<o.mx_idx) res[l]=c[l]+query(1,-2,q-1,o.mx_idx+1,q-1);
else res[l]=query(1,-2,q-1,o.mn_idx+1,q-1);
}
else
{
int m=mid(l,r);
solve(2*idx,l,m);
solve(2*idx+1,m+1,r);
}
for(int x:queries[idx]) update(1,-2,q-1,x,obj());
}
vector<int> distribute_candies(vector<int> nc,vector<int> nl,vector<int> nr,vector<int> nv)
{
n=nc.size();
for(int i=0;i<4*(n+5);i++) queries[i].clear();
tree.assign(4*(nl.size()+5),obj());
for(int i=0;i<n;i++) c[i]=nc[i];
q=nl.size();
for(int i=0;i<q;i++)
{
mv[i]=nv[i];
add_query(1,0,n-1,nl[i],nr[i],i);
}
update(1,-2,q-1,-2,obj(inf,-2));
update(1,-2,q-1,-1,obj(-inf,-1));
solve(1,0,n-1);
vector<int> r(n);
for(int i=0;i<n;i++) r[i]=res[i];
return r;
}
vector<int> bf(vector<int> nc,vector<int> nl,vector<int> nr,vector<int> nv)
{
n=nc.size();
q=nl.size();
vector<int> a(n);
for(int i=0;i<q;i++)
{
int l=nl[i];
int r=nr[i];
int x=nv[i];
for(int j=l;j<=r;j++) a[j]=clamp(a[j]+x,0,nc[j]);
}
return a;
}
//int main()
//{
// mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());
// auto rng=[&](int l,int r)->int{return uniform_int_distribution<int>(l,r)(gen);};
// while(1)
// {
// n=rng(1,100);
// q=rng(1,200);
// vector<int> cap(n);
// for(int i=0;i<n;i++) cap[i]=rng(1,10);
// vector<int> l(q),r(q),v(q);
// for(int i=0;i<q;i++)
// {
// l[i]=rng(0,n-1);
// r[i]=rng(l[i],n-1);
// v[i]=(rng(0,1)==0?-1:1)*rng(1,10);
// }
// vector<int> one=distribute_candies(cap,l,r,v);
// vector<int> two=bf(cap,l,r,v);
// if(one==two) cout << "OK" << endl;
// else
// {
// cout << n << "\n";
// for(int i=0;i<n;i++) cout << cap[i] << " \n"[i==n-1];
// cout << q << "\n";
// for(int i=0;i<q;i++) cout << l[i] << " " << r[i] << " " << v[i] << "\n";
// cout << "Received: ";
// for(int i=0;i<n;i++) cout << one[i] << " \n"[i==n-1];
// cout << "Expected: ";
// for(int i=0;i<n;i++) cout << two[i] << " \n"[i==n-1];
// break;
// }
// }
//// int n;
//// cin >> n;
//// vector<int> nc(n);
//// for(int i=0;i<n;i++) cin >> c[i];
//// int q;
//// cin >> q;
//// vector<int> l(q),r(q),v(q);
//// for(int i=0;i<q;i++) cin >> l[i] >> r[i] >> v[i];
//// vector<int> x=distribute_candies(nc,l,r,v);
//// for(int i=0;i<n;i++) cout << x[i] << " \n"[i==n-1];
// return 0;
//}
