#include <bits/stdc++.h>
#define ll long long
#define sz(x) int(x.size())
#define forn(i, n) for (i = 0; i < n; i++)
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define fr first
#define se second
using namespace std;
ll inMa2 = LLONG_MIN, inMa1 = 0;
ll inMi2=LLONG_MAX, inMi1=0;
struct nodo
{
ll sum = 0, lazy = 0, ma1 = inMa1, ma2 = inMa2, tam = 0, cma1 = 0, cma2 = 0;
ll mi1=inMi1, mi2=inMi2, cmi1=0, cmi2=0;
bool laz=0, laz2=0;
};
vector<ll> I, D;
vector<nodo> seg;
ll pot = 1, n, q;
void newMa1(ll nod, ll val)
{
seg[nod].sum -= seg[nod].cma1 * seg[nod].ma1;
seg[nod].ma1 = val;
seg[nod].sum += seg[nod].cma1 * seg[nod].ma1;
seg[nod].laz=1;
}
void newMi1(ll nod, ll val)
{
seg[nod].sum-=seg[nod].cmi1*seg[nod].mi1;
seg[nod].mi1=val;
seg[nod].sum+=seg[nod].cmi1*seg[nod].mi1;
seg[nod].laz2=1;
}
void act(ll nod, ll val)
{
ll pad = nod / 2;
seg[nod].sum += val * seg[nod].tam;
seg[nod].lazy += val;
if(seg[nod].ma1!=inMa2)
seg[nod].ma1 += val;
if(seg[nod].ma2!=inMa2)
seg[nod].ma2 += val;
if(seg[nod].mi1!=inMi2)
seg[nod].mi1+=val;
if(seg[nod].mi2!=inMi2)
seg[nod].mi2+=val;
}
void chmin(ll nod, ll val);
void chmax(ll nod, ll val);
void prop(ll nod)
{
act(nod * 2, seg[nod].lazy);
act(nod * 2 + 1, seg[nod].lazy);
seg[nod].lazy = 0;
if(seg[nod].laz)
{
chmin(nod*2,seg[nod].ma1);
chmin(nod*2+1,seg[nod].ma1);
}
if(seg[nod].laz2)
{
chmax(nod*2,seg[nod].mi1);
chmax(nod*2+1,seg[nod].mi1);
}
seg[nod].laz=0;
seg[nod].laz2=0;
}
ll sum(ll nod, ll x)
{
ll ret = 0;
for (ll i = 0; i < 2; i++)
{
if (seg[nod * 2 + i].ma1 == x)
ret = ret + seg[nod * 2 + i].cma1;
if (seg[nod * 2 + i].ma2 == x)
ret = ret + seg[nod * 2 + i].cma2;
}
return ret;
}
ll sum2(ll nod, ll x)
{
ll ret = 0;
for (ll i = 0; i < 2; i++)
{
if (seg[nod * 2 + i].mi1 == x)
ret = ret + seg[nod * 2 + i].cmi1;
if (seg[nod * 2 + i].mi2 == x)
ret = ret + seg[nod * 2 + i].cmi2;
}
return ret;
}
void up(ll nod)
{
vector<ll> v = {seg[nod * 2].ma1, seg[nod * 2 + 1].ma1, seg[nod * 2].ma2, seg[nod * 2 + 1].ma2};
sort(all(v));
auto it =unique(all(v));
ll fin = (it-v.begin())-1, i;
seg[nod].ma1 = v[fin];
fin--;
if (fin >= 0)
seg[nod].ma2 = v[fin];
else
seg[nod].ma2 = inMa2;
seg[nod].cma1 = sum(nod, seg[nod].ma1);
seg[nod].cma2 = sum(nod, seg[nod].ma2);
seg[nod].sum = seg[nod * 2].sum + seg[nod * 2 + 1].sum;
v = {seg[nod * 2].mi1, seg[nod * 2 + 1].mi1, seg[nod * 2].mi2, seg[nod * 2 + 1].mi2};
sort(all(v));
it =unique(all(v));
fin = (it-v.begin())-1;
seg[nod].mi1=v[0];
seg[nod].cmi1=sum2(nod,seg[nod].mi1);
if(fin>0)
seg[nod].mi2=v[1];
else
seg[nod].mi2=inMi2;
seg[nod].cmi2 = sum2(nod, seg[nod].mi2);
}
void update(ll l, ll r, ll nod, ll val)
{
if (I[nod] > r || D[nod] < l)
return;
if (I[nod] >= l && D[nod] <= r)
{
act(nod, val);
return;
}
prop(nod);
update(l, r, nod * 2, val);
update(l, r, nod * 2 + 1, val);
up(nod);
}
ll calc(ll l, ll r, ll nod)
{
if (I[nod] > r || D[nod] < l)
return 0;
if (I[nod] >= l && D[nod] <= r)
return seg[nod].sum;
prop(nod);
ll ret = calc(l, r, nod * 2) + calc(l, r, nod * 2 + 1);
return ret;
}
void chmin(ll nod, ll val)
{
if (seg[nod].ma1 <= val)
return;
if (seg[nod].ma2 < val)
{
newMa1(nod, val);
if(seg[nod].mi1>val)
{
seg[nod].mi1=val;
seg[nod].laz2=1;
}
return;
}
prop(nod);
chmin(nod * 2, val);
chmin(nod * 2 + 1, val);
up(nod);
}
void chmax(ll nod, ll val)
{
if(seg[nod].mi1>=val)
return;
if(seg[nod].mi2>val)
{
newMi1(nod,val);
if(seg[nod].ma1<val)
{
seg[nod].ma1=val;
seg[nod].laz=1;
}
return;
}
prop(nod);
chmax(nod*2,val);
chmax(nod*2+1,val);
up(nod);
}
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l, std::vector<int> r, std::vector<int> v)
{
ll i;
n = sz(c);
q = sz(l);
while (pot < n)
pot *= 2;
seg.resize(pot * 2);
I.resize(pot * 2);
D.resize(pot * 2);
for (i = pot; i < pot * 2; i++)
{
I[i] = D[i] = i;
seg[i].ma1=inMa2;
seg[i].mi1=inMi2;
}
for (i = 0; i < n; i++)
{
seg[i+pot].ma1=0;
seg[i+pot].mi1=0;
seg[i+pot].cmi1=seg[i + pot].cma1 = seg[i + pot].tam = 1;
}
for (i = pot - 1; i > 0; i--)
{
I[i] = I[i * 2];
D[i] = D[i * 2 + 1];
seg[i].cmi1=seg[i].cma1 = seg[i].tam = seg[i * 2].tam + seg[i * 2 + 1].tam;
}
for (i = 0; i < q; i++)
{
update(l[i] + pot, r[i] + pot, 1, v[i]);
chmin(1,c[0]);
chmax(1,0);
}
vector<int>ans(n);
for(i=0; i<n; i++)
ans[i]=calc(i+pot,i+pot,1);
return ans;
}
