template struct LazySegmentTree { int n; vector info; vector tag; LazySegmentTree(vector init) { n = init.size(); info.assign(4 * n, Info()); tag.assign(4 * n, Tag()); function build = [&](int p, int l, int r) { if (l == r) { info[p] = init[l - 1]; return; } int m = (l + r) / 2; build(2 * p, l, m); build(2 * p + 1, m + 1, r); pull(p); }; build(1, 1, n); } void pull(int p) { info[p] = info[2 * p] + info[2 * p + 1]; } void apply(int p, const Tag &v) { info[p].apply(v); tag[p].apply(v); } void push(int p) { apply(2 * p, tag[p]); apply(2 * p + 1, tag[p]); tag[p] = Tag(); } void rangeApply(int p, int l, int r, int x, int y, const Tag &v) { if (l > y || r < x) return; if (l >= x && r <= y) { apply(p, v); return; } push(p); int m = (l + r) / 2; rangeApply(2 * p, l, m, x, y, v); rangeApply(2 * p + 1, m + 1, r, x, y, v); pull(p); } Info rangeQuery(int p, int l, int r, int x, int y) { if (l > y || r < x) return Info(); if (l >= x && r <= y) return info[p]; push(p); int m = (l + r) / 2; return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m + 1, r, x, y); } }; struct Tag { LL x; Tag(LL x = 0) { this->x = x; } void apply(const Tag &t) { x += t.x; } }; struct Info { LL x, l, r; Info(LL x = 0, LL l = 0, LL r = 0) { this->x = x; this->l = l; this->r = r; } void apply(const Tag &t) { if (t.x) x += t.x * (r - l + 1); } }; Info operator+(const Info &a, const Info &b) { return Info(a.x + b.x, a.l, b.r); }