做这道题本意是为了补CCPC秦皇岛热身赛C，也就是2022 CCPC 华为云计算挑战赛 机器人那题
先考虑一个盒子怎么做，并且不考虑限制
那样的话可以得到时刻和盒子内球的数量的图像，考虑由这个不加限制的图像推出加上限制的实际答案
完整的图像一定是极大值极小值交错，考虑两个相邻的极大值和极小值，玩一下发现我们只关心它们之间差值是否大于限制 c-0
如果大于等于c了，那么时间上靠后出现的这个极大（小）值一定是触顶（底）的，最后求答案分类讨论一下就好
那么最后其实就是找最短的满足这个条件的后缀，发现这个不太好实现，其实上面描述的不够准确，我们关心的不是两个极值间怎么样，而是一段区间内的最大值和最小值之间距离是否大于等于c
对于最短的满足这个条件的后缀，左端点一定是这个后缀的最大值或最小值，根据左端点是最大值还是最小值分类讨论即可，这个可以二分解决
如果找不到满足条件的后缀，也就是整个区间都不满足，把负的值加回去就是结果
代码：
#include <bits/stdc++.h>
#define ls (x << 1)
#define rs (x << 1 | 1)
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int MAX_N = 2e5 + 10;
const LL MAX_V = 1e15, MIN_V = -1e15;
struct NODE{
LL sum, maxv, minv, lzy;
NODE(LL a = 0, LL b = 0, LL c = 0, LL d = 0) : sum{a}, maxv{b}, minv{c}, lzy{d} {}
};
struct SGT{
NODE t[MAX_N << 2];
void pushup(int x) {
t[x].maxv = max(t[ls].maxv, t[rs].maxv);
t[x].minv = min(t[ls].minv, t[rs].minv);
}
NODE Merge(NODE l, NODE r) {
return NODE(0, max(l.maxv, r.maxv), min(l.minv, r.minv), 0);
}
void pushdown(int x) {
LL v = t[x].lzy; t[x].lzy = 0;
t[ls].lzy += v; t[ls].sum += v; t[ls].maxv += v; t[ls].minv += v;
t[rs].lzy += v; t[rs].sum += v; t[rs].maxv += v; t[rs].minv += v;
}
void update(int L, int R, int l, int r, int x, int v) {
if (L <= l && r <= R) {
t[x].lzy += v; t[x].maxv += v; t[x].minv += v; t[x].sum += v;
return;
}
pushdown(x);
int mid = l + r >> 1;
if (L <= mid) update(L, R, l, mid, ls, v);
if (mid < R) update(L, R, mid + 1, r, rs, v);
pushup(x);
}
LL getv(int D, int l, int r, int x) {
if (l == r) return t[x].sum;
pushdown(x);
int mid = l + r >> 1;
if (D <= mid) return getv(D, l, mid, ls);
else return getv(D, mid + 1, r, rs);
}
LL query(int l, int r, int x, LL top, NODE suf) {
if (l == r) {
NODE cur = Merge(t[x], suf);
if (cur.maxv - cur.minv <= top) return -cur.minv;
if (cur.minv == t[x].minv)return top - cur.maxv;
if (cur.maxv == t[x].maxv) return -cur.minv;
}
pushdown(x);
int mid = l + r >> 1;
NODE nxt = Merge(t[rs], suf);
if (nxt.maxv - nxt.minv > top) return query(mid + 1, r, rs, top, suf);
else return query(l, mid, ls, top, nxt);
}
}sgt;
vector<PII> opt[MAX_N];
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
int n = c.size(), q = l.size();
for (int i = 0; i < q; ++i) {
opt[l[i]].push_back({i + 1, v[i]});
opt[r[i] + 1].push_back({i + 1, -v[i]});
}
vector<int> ret(n);
for (int i = 0; i < n; ++i) {
for (auto x : opt[i]) {
sgt.update(x.first, q, 0, q, 1, x.second);
}
NODE suf = NODE(0, MIN_V, MAX_V, 0);
ret[i] = int(sgt.query(0, q, 1, c[i], suf) + sgt.getv(q, 0, q, 1));
}
return ret;
}