Luogu P8518 [IOI2021] 分糖果

题目链接

 做这道题本意是为了补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;
}