//Place your snippets for cpp here. Each snippet is defined under a snippet name and has a prefix, body and 
// description. The prefix is what is used to trigger the snippet and the body will be expanded and inserted. Possible variables are:
// $1, $2 for tab stops, $0 for the final cursor position, and ${1:label}, ${2:another} for placeholders. Placeholders with the 
// same ids are connected.
// prefix 的格式要求是 acm-[一级标题编号].[二级标题编号][该代码片段的英文简称]
// description 的格式要求是 "插入 [该代码片段的中文名]"

{
    "线段树": {
        "prefix": "acm-2.6LazySegmentTree-full",
        "body": [
            "template<class Info, class Tag> struct LazySegmentTree {",
            "    int n;",
            "    vector<Info> info;",
            "    vector<Tag> tag;",
            "    LazySegmentTree(vector<Info> init) {",
            "        n = init.size();",
            "        info.assign(4 * n, Info());",
            "        tag.assign(4 * n, Tag());",
            "        function<void(int, int, int)> 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); }"
        ],
        "description": "插入 线段树"
    }
}