#include "candies.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,q;
const int N=2e5+10;
ll dif[N];
struct Data
{
int mx[3]={0},mi[3]={0};
ll lzy[3]={0};
} seg[N<<2];
Data merge(Data &a,Data& b)
{
Data res;
for(int j=0;j<3;j++)
{
res.mx[j]=((a.mx[j]>b.mx[j])?a.mx[j]:b.mx[j]);
res.mi[j]=((a.mi[j]<b.mi[j])?a.mi[j]:b.mi[j]);
}
return res;
}
Data SeT(int c)
{
int h=c,f=0;
Data res;
res.mi[0]=res.mx[0]=h-f;
res.mi[1]=res.mx[1]=h-c-f;
res.mi[2]=res.mx[2]=c;
return res;
}
void push(int v,int l,int r) // c never changes
{
int lc=v<<1,rc=lc|1;
if(seg[v].lzy[0])
{
seg[v].mi[0]=seg[v].mx[0]=0;
seg[v].mi[1]=-seg[v].mx[2];
seg[v].mx[1]=-seg[v].mi[2];
if(l!=r)
{
seg[lc].lzy[0]=seg[lc].lzy[1]=seg[lc].lzy[2]=0;
seg[rc].lzy[0]=seg[rc].lzy[1]=seg[rc].lzy[2]=0;
seg[lc].lzy[0]=seg[rc].lzy[0]=1;
}
seg[v].lzy[0]=0;
}
if(seg[v].lzy[1])
{
seg[v].mi[1]=seg[v].mx[1]=0;
seg[v].mi[0]=seg[v].mi[2];
seg[v].mx[0]=seg[v].mx[2];
if(l!=r)
{
seg[lc].lzy[0]=seg[lc].lzy[1]=seg[lc].lzy[2]=0;
seg[rc].lzy[0]=seg[rc].lzy[1]=seg[rc].lzy[2]=0;
seg[lc].lzy[1]=seg[rc].lzy[1]=1;
}
seg[v].lzy[1]=0;
}
if(seg[v].lzy[2])
{
seg[v].mi[0]-=seg[v].lzy[2];
seg[v].mx[0]-=seg[v].lzy[2];
seg[v].mi[1]-=seg[v].lzy[2];
seg[v].mx[1]-=seg[v].lzy[2];
if(l!=r)
{
seg[lc].lzy[2]+=seg[v].lzy[2];
seg[rc].lzy[2]+=seg[v].lzy[2];
}
seg[v].lzy[2]=0;
}
}
void Build(vector<int>&c ,int l=1,int r=n,int v=1)
{
if(l==r)
{
seg[v]=SeT(c[l-1]);
return;
}
int m=(l+r)>>1,lc=v<<1,rc=lc|1;
Build(c,l,m,lc);
Build(c,m+1,r,rc);
seg[v]=merge(seg[lc],seg[rc]);
}
void Update(int ql,int qr,int qv,int l=1,int r=n,int v=1)
{
push(v,l,r); // causing all lzy to become zero
if(qr<l or r<ql)return;
if(ql<=l and r<=qr and seg[v].mx[0]<=qv) // all moving to right border
{
seg[v].lzy[0]=1;
// we need to set the seg[v].mx[0]=0
push(v,l,r);
return;
}
if(ql<=l and r<=qr and qv<=seg[v].mi[1]) // all moving to right border
{
seg[v].lzy[1]=1;
push(v,l,r);
// we need to set the seg[v].mi[1]=0
return;
}
if(ql<=l and r<=qr and seg[v].mx[1]<=qv and qv<=seg[v].mi[0]) // all moving to right border
{
seg[v].lzy[2]+=qv;
push(v,l,r);
// we need to set the seg[v].mi[1]=0
return;
}
//qv<=seg[v].mi[1]
int m=(l+r)>>1,lc=v<<1,rc=lc|1;
Update(ql,qr,qv,l,m,lc);
Update(ql,qr,qv,m+1,r,rc);
seg[v]=merge(seg[lc],seg[rc]);
}
int GeT(int i,int l=1,int r=n,int v=1)
{
push(v,l,r);
if(l==r)
{
return seg[v].mx[1];
}
int m=(l+r)>>1;
if(i<=m)
return GeT(i,l,m,v<<1);
return GeT(i,m+1,r,2*v+1);
}
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,std::vector<int> r, std::vector<int> v) {
n = c.size();
q=l.size();
vector<int> fnl(n,0);
for(int i=0;i<n;i++)
{
vector<ll> val(q+2,0);
for(int j=0;j<q;j++)
{
val[j+1]=val[j];
if(l[j]<=i and i<=r[j])
{
val[j+1]+=v[j];
}
}
}
}
