遅延SegTree

色々隠蔽の方法を考えています。

これはなんかごついね

#include <bits/stdc++.h>

using namespace std;
using uint = unsigned int;
template<class T> using V = vector<T>;

template<class OP>
struct SegTree {
    using D = typename OP::D;
    using L = typename OP::L;
    static constexpr auto e_d = OP::e_d;
    static constexpr auto e_l = OP::e_l;
    static constexpr auto op_dd = OP::op_dd;
    static constexpr auto op_dl = OP::op_dl;
    static constexpr auto op_ll = OP::op_ll;

    int sz, lg; //(2^lgに拡張後の)サイズ, lg
    V<D> d;
    V<L> lz;

    SegTree(int n) : SegTree(V<D>(n, e_d())) {}
    SegTree(V<D> first) {
        int n = int(first.size());
        lg = 1;
        while ((1<<lg) < n) lg++;
        sz = 1<<lg;
        d = V<D>(2*sz, e_d());
        lz = V<L>(2*sz, e_l());
        for (int i = 0; i < n; i++) d[sz + i] = first[i];
        for (int i = sz-1; i >= 0; i--) {
            update(i);
        }
    }

    void all_add(int k, L x) {
        d[k] = op_dl(d[k], x);
        lz[k] = op_ll(lz[k], x);
    }
    void push(int k) {
        all_add(2*k, lz[k]);
        all_add(2*k+1, lz[k]);
        lz[k] = e_l();
    }
    void update(int k) {
        d[k] = op_dd(d[2*k], d[2*k+1]);
    }

    D sum(int a, int b, int l, int r, int k) {
        if (b <= l || r <= a) return e_d();
        if (a <= l && r <= b) return d[k];
        push(k);
        int mid = (l + r) / 2;
        return op_dd(sum(a, b, l, mid, 2*k), sum(a, b, mid, r, 2*k+1));
    }
    D sum(int a, int b) { return sum(a, b, 0, sz, 1); }

    void add(int a, int b, L x, int l, int r, int k) {
        if (b <= l || r <= a) return;
        if (a <= l && r <= b) {
            all_add(k, x);
            return;
        }
        push(k);
        int mid = (l + r) / 2;
        add(a, b, x, l, mid, 2*k); add(a, b, x, mid, r, 2*k+1);
        update(k);
    }
    void add(int a, int b, L x) { add(a, b, x, 0, sz, 1); }

};

//starry sky tree
struct OP {
    using D = int;
    using L = int;
    static constexpr D e_d() { return (1<<30) - 1000; }
    static constexpr L e_l() { return 0; }
    static int op_dd(D l, L r) { return min(l, r); }
    static int op_dl(D l, L r) { return l + r; }
    static int op_ll(D l, L r) { return l + r; }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    auto seg = SegTree<OP>(V<int>(n, 0));
    for (int i = 0; i < q; i++) {
        int ty, x, y;
        cin >> ty >> x >> y; y++;
        if (ty == 0) {
            int z;
            cin >> z;
            seg.add(x, y, z);
        } else {
            cout << seg.sum(x, y) << endl;
        }
    }
    return 0;
}