动态开点线段树
unknown
c_cpp
2 years ago
1.4 kB
13
Indexable
Never
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; } };