遅延Segtree2

イロモノにしか見えないと思いきや案外いいのでは？

#include <bits/stdc++.h>

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

//template<class D, class L, auto op_dd, auto op_dl, auto op_ll> (since c++17)
template<class D, class L, D (*op_dd)(D, D), L (*op_dl)(D, L), L (*op_ll)(L, L)>
struct SegTree {
    int sz, lg; //(2^lgに拡張後の)サイズ, lg
    D e_d; V<D> d;
    L e_l; V<L> lz;

    SegTree(int n, D e_d, L e_l) : SegTree(V<D>(n, e_d), e_d, e_l) {}
    SegTree(V<D> first, D _e_d, L _e_l) : e_d(_e_d), e_l(_e_l) {
        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); }

};

int my_min(int a, int b) { return min(a, b); }
int add(int a, int b) { return a + b; }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    auto seg = SegTree<int, int, my_min, add, add>(V<int>(n, 0), (1<<30) - 1000, 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;
}