动态开点线段树

struct Node {
    int v, lz, ls, rs;
    Node(): v(0), lz(0), ls(0), rs(0) {}
};
class SegTree {
    vector<Node> tr;
    int cnt;
    void push_down(int p, int len) {
        if (!tr[p].ls) tr[p].ls = ++cnt, tr.emplace_back(Node{});
        if (!tr[p].rs) tr[p].rs = ++cnt, tr.emplace_back(Node{});
        if (!tr[p].lz) return;
        int lz = tr[p].lz;
        tr[tr[p].ls].v = len / 2 * lz;
        tr[tr[p].rs].v = (len - len / 2) * lz;
        tr[tr[p].ls].lz = tr[tr[p].rs].lz = lz;
        tr[p].lz = 0;
    }
    void push_up(int p) {
        tr[p].v = tr[tr[p].ls].v + tr[tr[p].rs].v;
    }
public:
    SegTree(): tr(1), cnt(0) {
        tr.reserve(500000);
    }

    void modify(int l, int r, int L, int R, int v, int p = 0) {
        if (l <= L && r >= R) {
            tr[p].lz = v, tr[p].v = v * (R - L + 1);
            return;
        }
        int mid = (L + R - 1) / 2;
        push_down(p, R - L + 1);
        if (mid >= l) modify(l, r, L, mid, v, tr[p].ls);
        if (mid < r) modify(l, r, mid + 1, R, v, tr[p].rs);
        push_up(p);
    }

    int query(int l, int r, int L, int R, int p = 0) {
        if (l <= L && r >= R) return tr[p].v;
        int mid = (L + R - 1) / 2, ret = 0;
        push_down(p, R - L + 1);
        if (mid >= l) ret += query(l, r, L, mid, tr[p].ls);
        if (mid < r) ret += query(l, r, mid + 1, R, tr[p].rs);
        return ret;
    }
};