线段树模板

struct SegmentTree {
    void pushUp(int u) {
        maxv[u] = std::max(maxv[u << 1], maxv[u << 1 | 1]);
    }

    void coverDown(int u) {
        if (lz1[u] != -1e14) {
            lz2[u << 1] = lz2[u << 1 | 1] = 0;
            lz1[u << 1] = lz1[u << 1 | 1] = lz1[u];
            maxv[u << 1] = maxv[u << 1 | 1] = lz1[u];
            lz1[u] = -1e14;
        }
    }
    void addDown(int u) {
        if (lz2[u]) {
            coverDown(u);
            lz2[u << 1] += lz2[u], lz2[u << 1 | 1] += lz2[u];
            maxv[u << 1] += lz2[u], maxv[u << 1 | 1] += lz2[u];
            lz2[u] = 0;
        }
    }
    void pushDown(int u) {
        // 1.将父节点的懒标记传递给子节点
        // 2.用更新后的子节点标记计算子节点所维护的信息
        // 3.将父节点懒标记清空
        coverDown(u);
        addDown(u);
    }

    void build(int u, int l, int r) {
        // 给标记赋予初始值
        lz1[u] = -1e14, lz2[u] = 0;
        if (l == r) {
            maxv[u] = a[l];
            return;
        }
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        // 维护信息的更新
        pushUp(u);
    }

    // 区间修改操作
    void modify1(int u, int l, int r, int tl, int tr, int x) {
        if (l >= tl && r <= tr) {
            // 1.对该点的懒标记进行更新
            // 2.对该点所维护的信息进行更新
            // 注意标记的更新顺序，如果其他标记的存在会影响当前的更新，先进行 pushDown 操作
            lz2[u] = 0, lz1[u] = x;
            maxv[u] = x;
            return;
        }
        // 如果有懒标记的话在此处进行 pushDown 操作
        pushDown(u);
        int mid = l + r >> 1;
        if (tl <= mid) {
            modify1(u << 1, l, mid, tl, tr, x);
        }
        if (tr > mid) {
            modify1(u << 1 | 1, mid + 1, r, tl, tr, x);
        }
        // pushUp 更新所维护的信息
        pushUp(u);
    }
    void modify2(int u, int l, int r, int tl, int tr, int x) {
        if (l >= tl && r <= tr) {
            // 1.对该点的懒标记进行更新
            // 2.对该点所维护的信息进行更新
            // 注意标记的更新顺序，如果其他标记的存在会影响当前的更新，先进行 pushDown 操作
            coverDown(u);
            lz2[u] += x;
            maxv[u] += x;
            return;
        }
        // 如果有懒标记的话在此处进行 pushDown 操作
        pushDown(u);
        int mid = l + r >> 1;
        if (tl <= mid) {
            modify2(u << 1, l, mid, tl, tr, x);
        }
        if (tr > mid) {
            modify2(u << 1 | 1, mid + 1, r, tl, tr, x);
        }
        // pushUp 更新所维护的信息
        pushUp(u);
    }

    // 区间查询操作
    int query(int u, int l, int r, int tl, int tr) {
        if (l >= tl && r <= tr) {
            // 返回所查询的信息
            return maxv[u];
        }
        // 如果有懒标记在此处进行 pushDown 操作
        pushDown(u);
        int mid = l + r >> 1;
        int res = -1e17;
        if (tl <= mid) {
            res = std::max(res, query(u << 1, l, mid, tl, tr));
        }
        if (tr > mid) {
            res = std::max(res, query(u << 1 | 1, mid + 1, r, tl, tr));
        }
        return res;
    }
};