区间修改懒标记线段树通用板子

template <class Info, class Tag>
class LazySegmentTree
{
public:
#define l(p) (p << 1)
#define r(p) (p << 1 | 1)
    int n;
    vector<Info> info;
    vector<Tag> tag;
    LazySegmentTree() : n(0){};
    LazySegmentTree(int _n)
    {
        init(_n);
    }
    LazySegmentTree(vector<Info> _init)
    {
        init(_init);
    }
    void init(int _n)
    {
        init(vector<Info>(_n));
    }
    void init(vector<Info> _init)
    {
        n = _init.size();
        info.assign(n << 2, Info()); // 为info开辟大小
        tag.assign(n << 2, Tag());   // 为tag开辟大小
        auto build = [&](auto self, int p, int l, int r)
        {
            if (l == r)
            {
                info[p] = _init[l];
                return;
            }
            int mid = l + r >> 1;
            self(self, l(p), l, mid);
            self(self, r(p), mid + 1, r);
            pushup(p);
        };
        build(build, 1, 1, n);
    }
    void pushup(int p)
    {
        info[p] = info[l(p)] + info[r(p)];
    }
    void apply(int p, const Tag &v, int len)
    {
        info[p].apply(v, len);
        tag[p].apply(v);
    }
    void pushdown(int p, int pl, int pr)
    { // 传入pl, pr计算区间长度
        int mid = pl + pr >> 1;
        apply(l(p), tag[p], mid - pl + 1);
        apply(r(p), tag[p], pr - mid);
        tag[p] = Tag(); // 设空
    }
    void modify(int p, int pl, int pr, int x, const Info &v)
    { // 单点修改
        if (pl == pr)
        {
            info[p] = v;
            return;
        }
        int mid = pl + pr >> 1;
        pushdown(p, pl, pr); // 传入pl, pr计算区间长度
        if (x <= mid)
            modify(l(p), pl, mid, x, v);
        else
            modify(r(p), mid + 1, pr, x, v);
        pushup(p);
    }
    void modify(int p, const Info &v)
    {
        modify(1, 1, n, p, v);
    }
    Info query(int L, int R, int p, int pl, int pr)
    {
        if (pl > R || pr < L)
            return Info();
        if (L <= pl && pr <= R)
            return info[p];
        int mid = pl + pr >> 1;
        pushdown(p, pl, pr); // 传入pl, pr计算区间长度
        return query(L, R, l(p), pl, mid) + query(L, R, r(p), mid + 1, pr);
    }
    Info query(int L, int R)
    {
        return query(L, R, 1, 1, n);
    }
    void modifyRange(int L, int R, int p, int pl, int pr, const Tag &v) // 区间修改
    {
        if (pl > R || pr < L)
            return;
        if (L <= pl && pr <= R)
        {
            apply(p, v, pr - pl + 1); // 传入区间长度
            return;
        }
        int mid = pl + pr >> 1;
        pushdown(p, pl, pr); // 传入pl, pr计算区间长度
        modifyRange(L, R, l(p), pl, mid, v);
        modifyRange(L, R, r(p), mid + 1, pr, v);
        pushup(p);
    }
    void modifyRange(int L, int R, const Tag &v)
    {
        return modifyRange(L, R, 1, 1, n, v);
    }
#undef l(p)
#undef r(p)
};

struct Tag {
    // 要维护的tag
    Tag(){} // 默认构造函数
    void apply(Tag t) {
        // 父tag怎么传到子tag
    }
};
struct Info {
    // 要维护的值
    void apply(Tag t, int len) {
        // tag怎么传到要维护的值
    }
};
Info operator+(Info a, Info b) {
    Info c;
    // 运算符重载
    return c;
}