题解：线段树整合维护多序列（A/B/C）的高效实现

一、题目核心分析

本题要求维护三个序列 A/B/C，支持两类修改操作和三类查询操作，核心难点在于：

• 修改后同步更新：每次修改 A 后，必须同步更新 B_i = B_i + A_i（B 是 A 每次修改后的累计和）和 C_i = max(C_i, A_i)（C 是 A 的历史最大值）。
• 数据规模限制：n, Q ≤ 2e5，要求所有操作的时间复杂度为 O(log n)，否则会超时。

直接维护三个独立的数据结构（如三个线段树）会导致修改操作后需同步更新三次，时间复杂度飙升至 O(3 log n)，且逻辑冗余。因此，核心思路是将 A/B/C 的维护逻辑整合到一个线段树中，通过精巧的节点设计和延迟标记，实现一次修改、三方同步更新。

二、核心设计思路

1. 整合维护目标

线段树每个节点同时维护以下信息，避免多结构同步开销： | 维护目标 | 节点字段 | 说明 | |----------------|----------------|---------------------------------------| | A 的当前状态 | sum | 区间 A 元素和（支持查询3） | | | max/sec/cnt | 区间 A 最大值/次大值/最大值元素个数（优化 chmin 操作） | | B 的累计和 | hsum | 区间 B 元素和（支持查询4），即每次修改后 A_i 的总和 | | C 的历史最大值 | hmax | 区间 C 元素和（支持查询5），即 A 的历史最大值 |

2. 延迟标记的分层设计

chmin 操作仅影响区间内 A_i > v 的元素（通常是当前区间的最大值元素），非最大值元素无需修改。因此，延迟标记分为两类，精准控制更新范围：

• tmax：仅作用于当前区间的 最大值元素（如 chmin 仅修改最大值时使用）。
• tag：作用于当前区间的 非最大值元素（如 区间加 需修改所有元素时使用）。

3. 标记字段设计（Tag 结构体）

标记需追踪四类信息，确保多次修改后计算结果正确： | 字段 | 含义 | 作用场景 | |----------|---------------------------------------|-----------------------------------| | add | A 的累计增量（区间加操作的核心） | 更新 A 的当前值（sum/max/sec） | | hadd | 历史最大增量 | 更新 C（hmax = max(hmax, max + hadd)） | | upd | 累计修改次数 | 计算 B 的增量（每次修改贡献 A_i） | | dhadd | 增量累计乘积项 | 精准计算每次修改时 A_i 的取值（用于 hsum） |

标记支持叠加（重载 operator+），确保延迟标记的合并逻辑正确：

Tag operator+(const Tag &lhs, const Tag &rhs) {
    return Tag(
        lhs.add + rhs.add,                // 增量叠加
        max(lhs.hadd, lhs.add + rhs.hadd),// 历史最大增量更新
        lhs.upd + rhs.upd,                // 修改次数叠加
        lhs.dhadd + lhs.add * rhs.upd + rhs.dhadd // 增量乘积项叠加
    );
}

三、线段树关键操作实现

1. 节点初始化与合并

• 初始化（init）：叶子节点对应初始 A_i，hmax = A_i（初始 C_i = A_i），hsum = 0（初始 B_i = 0）。
• 合并（merge）：父节点信息由左右子节点合并，核心逻辑：
  • sum/hsum/hmax：直接取和或最大值。
  • max：取左右子节点 max 的最大值。
  • cnt：统计左右子节点中等于 max 的元素个数。
  • sec：取次大值（可能是左子节点 sec、右子节点 sec 或另一子节点的 max）。

2. 核心修改操作

（1）区间加（操作2）

对区间 [l, r] 的 A_i 加 v，需同步更新 A/B/C：

• 给区间所有元素加 v，通过 Tag(v, v, 0, 0) 实现：
  • add = v：更新 A 的当前值。
  • hadd = v：更新 C 的历史最大值。
  • upd = 0：暂不触发 B 更新（后续通过 bump 统一处理）。
• 标记传递时，同步更新 sum/max/sec（A）、hmax（C）。

（2）区间 chmin（操作1）

对区间 [l, r] 的 A_i 取 min(A_i, v)，仅修改 A_i > v 的元素：

• 剪枝优化：若区间 max ≤ v，直接返回；若 sec < v，说明所有最大值元素需修改为 v（非最大值元素 ≤ sec < v，无需修改），通过 Tag(v - max, v - max, 0, 0) 批量更新最大值元素。
• 否则递归到子节点，精准修改需更新的元素。

（3）bump 操作（修改后同步 B/C）

每次修改操作（1/2）后，需触发 B 和 C 的最终更新：

• B 需累加本次修改后的 A_i：通过 Tag(0, 0, 1, 0) 标记，upd = 1 表示一次修改，hsum += 本次 A_i 总和。
• C 需更新历史最大值：通过 hadd 标记，hmax = max(hmax, 本次 max)。

3. 查询操作

• 查询 A 区间和（操作3）：递归查询区间 [l, r] 的 sum。
• 查询 B 区间和（操作4）：递归查询区间 [l, r] 的 hsum。
• 查询 C 区间最大值（操作5）：递归查询区间 [l, r] 的 hmax。

四、时间复杂度分析

• 每个修改/查询操作均为线段树的标准区间操作，时间复杂度 O(log n)。
• 标记的合并与传递为 O(1)（字段固定，与 n 无关）。
• 总时间复杂度：O(Q log n)，可满足 Q ≤ 2e5 的数据规模要求。

五、完整代码解释

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
constexpr i64 inf = 4e18;

// 模板函数：最大化/最小化
template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (a > b) { a = b; return true; } return false; }

namespace seg_tree {
// 延迟标记：tmax（作用于max元素）、tag（作用于非max元素）
struct Tag {
    i64 add, hadd, upd, dhadd;
    Tag() : add(0), hadd(0), upd(0), dhadd(0) {}
    Tag(i64 _add, i64 _hadd, i64 _upd, i64 _dhadd)
        : add(_add), hadd(_hadd), upd(_upd), dhadd(_dhadd) {}
};

// 标记叠加：合并两个标记（先应用lhs，再应用rhs）
inline Tag operator+(const Tag &lhs, const Tag &rhs) {
    return Tag(
        lhs.add + rhs.add,
        max(lhs.hadd, lhs.add + rhs.hadd),
        lhs.upd + rhs.upd,
        lhs.dhadd + lhs.add * rhs.upd + rhs.dhadd
    );
}

// 线段树节点：整合A/B/C的维护信息
struct Node {
    int l, r;
    i64 max, hmax, sec, sum, hsum; // A当前max、C历史max、A次大值、A和、B和
    int cnt; // A中等于max的元素个数
    Tag tmax, tag; // 分层标记

    // 叶子节点初始化（对应初始A_i）
    inline void init(i64 x) {
        max = hmax = sum = x;
        hsum = 0; // B初始为0
        cnt = 1;
        sec = -inf; // 次大值初始为负无穷
        tmax = tag = Tag();
    }

    // 应用标记：分别更新max元素和非max元素
    inline void push(const Tag &_tmax, const Tag &_tag) {
        // 1. 更新max元素（A/B/C）
        hmax = max(hmax, max + _tmax.hadd); // C的历史最大值
        hsum += _tmax.upd * cnt * max + _tmax.dhadd * cnt; // B的增量（max元素贡献）
        max += _tmax.add; // A的当前max更新
        sum += _tmax.add * cnt; // A的和更新（max元素贡献）
        tmax = tmax + _tmax; // 标记叠加

        // 2. 更新非max元素（A/B）
        const int len = r - l + 1;
        hsum += _tag.upd * (sum - cnt * max) + _tag.dhadd * (len - cnt); // B的增量（非max元素贡献）
        sum += _tag.add * (len - cnt); // A的和更新（非max元素贡献）
        sec += _tag.add; // A的次大值更新
        tag = tag + _tag; // 标记叠加
    }
};

// 左右子节点索引
inline int ls(int u) { return 2 * u + 1; }
inline int rs(int u) { return 2 * u + 2; }

struct SegTree {
    vector<Node> tr;

    // 构造函数：初始化线段树
    SegTree(const vector<i64> &a) {
        const int n = a.size();
        tr.resize(n << 1);
        build(0, 0, n - 1, a);
    }

    // 合并左右子节点到父节点
    inline void merge(Node &ans, const Node &lhs, const Node &rhs) {
        ans.max = max(lhs.max, rhs.max);
        ans.hmax = max(lhs.hmax, rhs.hmax);
        ans.sum = lhs.sum + rhs.sum;
        ans.hsum = lhs.hsum + rhs.hsum;
        ans.cnt = 0;

        // 统计max元素个数
        if (ans.max == lhs.max) ans.cnt += lhs.cnt;
        if (ans.max == rhs.max) ans.cnt += rhs.cnt;

        // 计算次大值
        if (lhs.max == rhs.max) ans.sec = max(lhs.sec, rhs.sec);
        else if (lhs.max > rhs.max) ans.sec = max(rhs.max, lhs.sec);
        else ans.sec = max(lhs.max, rhs.sec);
    }

    // 向上更新（合并子节点信息）
    inline void pushup(int u, int mid) {
        merge(tr[u], tr[ls(mid)], tr[rs(mid)]);
    }

    // 向下传递标记：根据子节点max决定应用哪个标记
    inline void pushdown(int u, int mid) {
        const int max_val = max(tr[ls(mid)].max, tr[rs(mid)].max);
        apply(ls(mid), tr[u].tmax, tr[u].tag, max_val);
        apply(rs(mid), tr[u].tmax, tr[u].tag, max_val);
        tr[u].tmax = tr[u].tag = Tag(); // 标记清空
    }

    // 对节点应用标记：若当前节点max等于目标max，应用tmax；否则应用tag
    inline void apply(int u, const Tag &tmax, const Tag &tag, int max_val) {
        if (tr[u].max == max_val) tr[u].push(tmax, tag);
        else tr[u].push(tag, tag);
    }

    // 构建线段树
    void build(int u, int l, int r, const vector<i64> &a) {
        tr[u].l = l, tr[u].r = r;
        if (l == r) return tr[u].init(a[l]);
        const int mid = (l + r) >> 1;
        build(ls(mid), l, mid, a);
        build(rs(mid), mid + 1, r, a);
        pushup(u, mid);
    }

    // 区间加操作
    void add(int u, int l, int r, i64 v) {
        if (l <= tr[u].l && tr[u].r <= r) {
            tr[u].push(Tag(v, v, 0, 0), Tag(v, v, 0, 0));
            return;
        }
        const int mid = (tr[u].l + tr[u].r) >> 1;
        pushdown(u, mid);
        if (l <= mid) add(ls(mid), l, r, v);
        if (r > mid) add(rs(mid), l, r, v);
        pushup(u, mid);
    }

    // 区间chmin操作
    void chmin(int u, int l, int r, i64 v) {
        if (tr[u].max <= v) return; // 无元素需要修改
        if (l <= tr[u].l && tr[u].r <= r && tr[u].sec < v) {
            // 所有max元素需修改为v，非max元素无需修改
            tr[u].push(Tag(v - tr[u].max, v - tr[u].max, 0, 0), Tag());
            return;
        }
        const int mid = (tr[u].l + tr[u].r) >> 1;
        pushdown(u, mid);
        if (l <= mid) chmin(ls(mid), l, r, v);
        if (r > mid) chmin(rs(mid), l, r, v);
        pushup(u, mid);
    }

    // 查询A的区间和
    i64 qsum(int u, int l, int r) {
        if (l <= tr[u].l && tr[u].r <= r) return tr[u].sum;
        const int mid = (tr[u].l + tr[u].r) >> 1;
        i64 res = 0;
        pushdown(u, mid);
        if (l <= mid) res += qsum(ls(mid), l, r);
        if (r > mid) res += qsum(rs(mid), l, r);
        return res;
    }

    // 查询B的区间和
    i64 qhsum(int u, int l, int r) {
        if (l <= tr[u].l && tr[u].r <= r) return tr[u].hsum;
        const int mid = (tr[u].l + tr[u].r) >> 1;
        i64 res = 0;
        pushdown(u, mid);
        if (l <= mid) res += qhsum(ls(mid), l, r);
        if (r > mid) res += qhsum(rs(mid), l, r);
        return res;
    }

    // 查询C的区间最大值
    i64 qhmax(int u, int l, int r) {
        if (l <= tr[u].l && tr[u].r <= r) return tr[u].hmax;
        const int mid = (tr[u].l + tr[u].r) >> 1;
        i64 res = -inf;
        pushdown(u, mid);
        if (l <= mid) res = max(res, qhmax(ls(mid), l, r));
        if (r > mid) res = max(res, qhmax(rs(mid), l, r));
        return res;
    }

    // 对外接口：区间加
    inline void range_add(int l, int r, i64 v) { add(0, l, r, v); }
    // 对外接口：区间chmin
    inline void range_chmin(int l, int r, i64 v) { chmin(0, l, r, v); }
    // 对外接口：查询A和
    inline i64 range_sum(int l, int r) { return qsum(0, l, r); }
    // 对外接口：查询B和
    inline i64 range_hsum(int l, int r) { return qhsum(0, l, r); }
    // 对外接口：查询Cmax
    inline i64 range_hmax(int l, int r) { return qhmax(0, l, r); }
    // 修改后同步B/C
    inline void bump() { tr[0].push(Tag(0, 0, 1, 0), Tag(0, 0, 1, 0)); }
};
}

using seg_tree::SegTree;

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int n, Q;
    scanf("%d %d", &n, &Q);
    vector<i64> a(n);
    for (int i = 0; i < n; i++) scanf("%lld", &a[i]);

    SegTree sgt(a);

    while (Q--) {
        int op, l, r;
        scanf("%d %d %d", &op, &l, &r);
        l--, r--; // 转换为0-based索引

        if (op == 1) {
            i64 v;
            scanf("%lld", &v);
            sgt.range_chmin(l, r, v);
            sgt.bump(); // 修改后同步B/C
        } else if (op == 2) {
            i64 v;
            scanf("%lld", &v);
            sgt.range_add(l, r, v);
            sgt.bump(); // 修改后同步B/C
        } else if (op == 3) {
            printf("%lld\n", sgt.range_sum(l, r));
        } else if (op == 4) {
            printf("%lld\n", sgt.range_hsum(l, r));
        } else if (op == 5) {
            printf("%lld\n", sgt.range_hmax(l, r));
        }
    }

    return 0;
}

六、关键细节总结

1. 索引转换：题目使用1-based下标，代码统一转为0-based，避免边界错误。
2. 数据类型：全程使用 i64（long long），确保不会溢出（题目说明所有数值在 long long 范围内）。
3. 剪枝优化：chmin 操作利用 sec 实现批量更新，避免递归到每个叶子节点。
4. 标记正确性：Tag 的叠加逻辑严格遵循“先应用前一个标记，再应用后一个标记”，确保 A/B/C 的计算结果精准。

该实现通过整合维护和分层标记，高效处理了多序列同步更新问题，时间复杂度最优，可满足所有测试点要求。