[补题][梦熊 CSP-S 2024 模拟赛] P11217 【MX-S4-T1】「yyOI R2」youyou 的垃圾桶

第一次遇到树上二分，记录一下。

说实话要是今年 CSP-S T1 出这个难度我可以在考场上上吊了。。。

这是赛后补的.jpg

看 dalao 们写的题解有点懵，花了亿点时间理解，所以这篇是 带注释ver.

题目

https://www.luogu.com.cn/problem/P11217

题意很好理解，但是要注意数据范围，由于所有数据不会有负数，所以就用 unsigned long long 好了。

思路

• 20pts：模拟，只用线段树不用树上二分和模拟一样的（我就是只套了线段树.jpg）
• 100pts：线段树 + 树上二分

代码

#include <iostream>
#include <vector>

#define ull unsigned long long // 不开 long long 会爆

class SegmentTree { // 线段树
private:
    struct Node {
        ull sum;
        ull lazy;
        Node *left, *right;
        Node() : sum(0), lazy(0), left(nullptr), right(nullptr) {};
    };
    
    std::vector<ull> init_vals;
    Node *root;
    ull n;
    
    Node *_build(ull begin, ull end) {
        Node *curr = new Node();
        if (begin == end) {
            curr->sum = init_vals.at(begin);
            return curr;
        }
        ull mid = begin + (end - begin) / 2;
        curr->left = _build(begin, mid);
        curr->right = _build(mid + 1, end);
        curr->sum = curr->left->sum + curr->right->sum;
        return curr;
    }
    
    void _push(Node *curr, ull begin, ull end, ull mid) { // 标准的 tag 下传
        if (begin == end) return;
        if (curr->lazy == 0) return;
        curr->left->lazy += curr->lazy;
        curr->right->lazy += curr->lazy;
        curr->left->sum += (mid - begin + 1) * curr->lazy;
        curr->right->sum += (end - mid) * curr->lazy;
        curr->lazy = 0;
    }

    ull _query_bs(Node *curr, ull begin, ull end, ull w, ull p) { // 树上二分，w 剩余生命值， p 要翻多少倍， sum * p 攻击力 
        ull result = 0;
        if (begin == end) {
            result += (curr->sum * p < w ? 1 : 0); // 攻击力小于 w 返回 1 否则 0， 一定是大于，按题目意思等于情况不计数
            return result;
        }
        ull mid = begin + (end - begin) / 2;
        _push(curr, begin, end, mid);
        if (curr->left->sum * p < w) { // 左节点总攻击力 (curr->left->sum * p) 小于剩余生命值 (w)，一定是大于，按题目意思等于情况不计数
            result += mid - begin + 1; // 加上左节点覆盖的范围
            result += _query_bs(curr->right, mid + 1, end, (w - curr->left->sum * p), p); // 扫右节点， 剩余生命值减去左节点总攻击力
        } else { // 不然只扫左节点
            result += _query_bs(curr->left, begin, mid, w, p);
        }
        return result;
    }
    
    void _add(Node *curr, ull begin, ull end, ull l, ull r, ull d) { // 标准的区间加法
        if (begin > r || end < l) return;
        if (begin >= l && end <= r) {
            curr->lazy += d;
            curr->sum += (end - begin + 1) * d;
            return;
        }
        ull mid = begin + (end - begin) / 2;
        _push(curr, begin, end, mid);
        _add(curr->left, begin, mid, l, r, d);
        _add(curr->right, mid + 1, end, l, r, d);
        curr->sum = curr->left->sum + curr->right->sum;
    }
    
public:
    SegmentTree(std::vector<ull> _init_vals) {
        init_vals = _init_vals;
        n = _init_vals.size() - 1;
        root = _build(1, n);
    }

    ull query_bs(ull w, ull p) {
        return _query_bs(root, 1, n, w, p);
    }
    
    void add(ull l, ull r, ull d) {
        _add(root, 1, n, l, r, d);
    }

    ull total() { // 树的总攻击力
        return root->sum;
    }
};

ull sol(SegmentTree &seg, ull w, ull n) {
    ull result = 0;
    ull p = 1, tot = seg.total();
    while (w > tot) { // 一定是大于，按题目意思等于情况不计数
        w -= tot;
        p *= 2; // 翻倍计数
        tot *= 2; // 总攻击力翻倍
        result += n;
    }
    result += seg.query_bs(w, p); // 剩下的生命值再树上二分
    return result;
}

int main() {
    ull n, q, w;
    scanf("%llu%llu%llu", &n, &q, &w);
    
    std::vector<ull> a(n + 1);
    for (ull i = 1; i <= n; i++) scanf("%llu", &a[i]);
    
    SegmentTree seg(a);
    ull l, r, d;
    while (q--) {
        scanf("%llu%llu%llu", &l, &r, &d);
        seg.add(l, r, d);
        printf("%llu\n", sol(seg, w, n));
    }
    return 0;
}