Khong 阿姨正在给附近一所学校的学生准备 \(n\) 盒糖果。盒子的编号分别为 \(0\) 到 \(n - 1\)，开始时盒子都为空。第 \(i\) 个盒子 \((0 \leq i \leq n - 1)\) 至多可以容纳 \(c[i]\) 块糖果（容量为 \(c[i]\)）。
Khong 阿姨花了 \(q\) 天时间准备糖果盒。在第 \(j\) 天 \((0 \leq j \leq q - 1)\)，她根据三个整数 \(l[j]\)、 \(r[j]\) 和 \(v[j]\) 执行操作，其中 \(0 \leq l[j] \leq r[j] \leq n - 1\) 且 \(v[j] \neq 0\)。对于每个编号满足 \(l[j] \leq k \leq r[j]\) 的盒子 \(k\)：
-
如果 \(v[j] > 0\)，Khong 阿姨将糖果一块接一块地放入第 \(k\) 个盒子，直到她正好放了 \(v[j]\) 块糖果或者该盒子已满。也就是说，如果该盒子在这次操作之前已有 \(p\) 块糖果，那么在这次操作之后盒子将有 \(\min(c[k], p + v[j])\) 块糖果。
-
如果 \(v[j] < 0\)，Khong 阿姨将糖果一块接一块地从第 \(k\) 个盒子取出，直到她正好从盒子中取出 \(-v[j]\) 块糖果或者该盒子已空。也就是说，如果该盒子在这次操作之前已有 \(p\) 块糖果，那么在这次操作之后盒子将有 \(\max(0, p + v[j])\) 块糖果。
你的任务是求出 \(q\) 天之后每个盒子中糖果的数量。
约束条件
-
\(1 \le n \le 200 000\)
-
\(1 \le q \le 200 000\)
-
\(1 \le c[i] \le 10 ^ 9\) （对所有 \(0 \le i \le n - 1\)）
-
\(0 \le l[j] \le r[j] \le n - 1\)（对所有 \(0 \le j \le q - 1\)）
-
\(−10 ^ 9 \le v[j] \le 10 ^ 9\) , \(v[j] ≠ 0\)（对所有 \(0 \le j \le q - 1\)）
设 \(t_i\) 表示第 \(i\) 个时刻的不考虑上下界，有多少个糖果。
那么如果区间 \([l,r]\) 中的极差超过了 \(a_i\)，那么这里碰了上下界中的至少一个。而且靠后那一个一定是最后的碰顶或碰底。知道了最后的碰顶，那就好求最后的情况了。
所以可以扫描线，然后维护极差。每次询问线段树二分出来极差最靠后的极差超过 \(a_i\) 的位置。如果不存在极差超过 \(a_i\) 直接输出总和减去最小值即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define PLL pair<LL,int>
const int N=2e5+5;
const LL INF=1e18;
typedef long long LL;
PLL mn[N<<2],mx[N<<2];
vector<int>a;
LL tg[N<<2],s;
void pushdown(int o)
{
if(tg[o])
{
mx[o<<1].first+=tg[o],mx[o<<1|1].first+=tg[o];
mn[o<<1].first+=tg[o],mn[o<<1|1].first+=tg[o];
tg[o<<1]+=tg[o],tg[o<<1|1]+=tg[o];
tg[o]=0;
}
}
void upd(int o,int l,int r,int x,int y,LL z)
{
if(x<=l&&r<=y)
return mn[o].first+=z,tg[o]+=z,mx[o].first+=z,void();
pushdown(o);
int md=l+r>>1;
if(md>=x)
upd(o<<1,l,md,x,y,z);
if(md<y)
upd(o<<1|1,md+1,r,x,y,z);
mn[o]=min(mn[o<<1],mn[o<<1|1]);
mx[o]=max(mx[o<<1],mx[o<<1|1]);
}
void ask(int o,int l,int r,PLL sx,PLL sn,int x,int c)
{
if(l==r)
{
sx=max(sx,mx[o]);
sn=min(sn,mn[o]);
if(sx.first-sn.first>=c)
{
if(sx.second<sn.second)
a[x]=s-sn.first;
else
a[x]=s-sx.first+c;
}
else
a[x]=s-sn.first;
return;
}
pushdown(o);
int md=l+r>>1;
if(max(mx[o<<1|1],sx).first-min(mn[o<<1|1],sn).first>=c)
ask(o<<1|1,md+1,r,sx,sn,x,c);
else
ask(o<<1,l,md,max(sx,mx[o<<1|1]),min(sn,mn[o<<1|1]),x,c);
}
void build(int o,int l,int r)
{
mx[o].second=mn[o].second=l;
if(l==r)
return;
int md=l+r>>1;
build(o<<1,l,md);
build(o<<1|1,md+1,r);
}
vector<int>distribute_candies(vector<int>c,vector<int>l,vector<int>r,vector<int>v)
{
vector<PLL>g[N];
a.resize(c.size());
for(int i=0;i<l.size();i++)
{
g[l[i]].push_back(make_pair(v[i],i+1));
g[r[i]+1].push_back(make_pair(-v[i],i+1));
}
build(1,0,l.size());
for(int i=0;i<c.size();i++)
{
for(auto j:g[i])
upd(1,0,l.size(),j.second,l.size(),j.first),s+=j.first;
ask(1,0,l.size(),make_pair(-INF,0),make_pair(INF,0),i,c[i]);
}
return a;
}
``