扶苏的问题

形式化题目

有一个长度为 $n$ 的整数序列 $a$ ，初始值给定。给出 $q$ 次操作：

把区间 $[l,r]$ 内每个数修改为 $x$ ；
把区间 $[l,r]$ 内每个数加上 $x$ ；
询问区间 $[l,r]$ 内的最大值。

要求按顺序处理全部操作，并输出每次询问的答案。

思路

先看一个可以直接验证想法的朴素解：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-12 22:10
 * update_at: 2026-08-12 22:14
 */
// brute.cpp：小数据暴力解，直接逐项模拟区间赋值、区间加与区间最大值查询，用来理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;

int n, m;
long long a[MAXN]; // a[i] 表示第 i 个位置的当前值

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    for (int i = 1; i <= m; i++) {
        int op, l, r;
        cin >> op >> l >> r;
        if (op == 1) {
            // 区间赋值：逐项把值改成 x。
            long long x;
            cin >> x;
            for (int j = l; j <= r; j++) {
                a[j] = x;
            }
        } else if (op == 2) {
            // 区间加：逐项加上 x。
            long long x;
            cin >> x;
            for (int j = l; j <= r; j++) {
                a[j] += x;
            }
        } else {
            // 区间查询最大值：逐项比较。
            long long answer = -(1LL << 60);
            for (int j = l; j <= r; j++) {
                if (answer < a[j]) answer = a[j];
            }
            cout << answer << '\n';
        }
    }

    return 0;
}

brute.cpp 直接维护数组：操作 1 逐项赋值、操作 2 逐项加、操作 3 逐项比最大值，单次操作 $O(n)$ ，总复杂度 $O(nq)$ ，无法通过 $10^6$ 的数据。

关键观察有两点：

整段操作可以整体结算：区间最大值只依赖两半的最大值，而整段赋值、整段加对最大值的影响分别是"变成 $x$ "和"加 $x$ "，不需要逐个访问区间里的点。
两种懒标记的复合顺序：赋值"覆盖"加法，加法"叠加"到已有赋值上——先加后赋等价于只赋；先赋后加等价于赋成新值。于是节点上记一个赋值标记和一个加法标记，下传时先赋值、后加法。

于是用线段树 + 双懒标记：每个节点存区间最大值 tree，另有赋值懒标记 set_lazy、加法懒标记 add_lazy 和"是否有赋值标记"的布尔 has_set；区间操作完全覆盖一个节点时只改它的摘要和标记，等要进入子树时才把标记下传给两个儿子。

数学视角：为什么懒标记能成立

查询信息构成幺半群：区间最大值用 $\max$ 合并， $\max$ 满足结合律，且存在单位元 $-\infty$ （空区间的最大值、查询累加的初始值），所以区间最大值构成幺半群 $(\mathbb{Z} \cup \{-\infty\}, \max, -\infty)$ 。
两种更新都是摘要上的自同态：整段赋值 $\text{set}_x(m) = x$ 、整段加 $\text{add}_v(m) = m + v$ 都只依赖摘要 $m$ 本身，并且与 $\max$ 合并可交换：

\text{set}_x(\max(a, b)) = x = \max(\text{set}_x(a), \text{set}_x(b))

\text{add}_v(\max(a, b)) = \max(a, b) + v = \max(a + v, b + v) = \max(\text{add}_v(a), \text{add}_v(b))

这就是"不必下到叶子"的数学原因。赋值与加法复合就是两个自同态的复合： $\text{set}_x \circ \text{add}_v = \text{set}_x$ （赋值覆盖旧加法）， $\text{add}_v \circ \text{set}_x = \text{set}_{x+v}$ （加法改写赋值标记），正好对应 apply_set 清零 add_lazy、apply_add 在 has_set 时改写 set_lazy 两条规则。

下面这张图展示一棵规模为 8 的线段树，节点上的数字是它代表的区间：

任意操作区间都能拆成 $O(\log n)$ 个"整段节点"。例如查询/修改 $[2,7]$ 会命中 [2,2]、[3,4]、[5,6]、[7,7] 这几个整段节点，各花 $O(1)$ 结算，这就是 $O(\log n)$ 的来源：不需要访问区间内的每个点。

以样例 #1 为例，每次操作后的真实序列如下：

操作	位置 1 2 3 4 5 6	输出
初始	1 1 4 5 1 4
赋值 [1,2] 为 6	6 6 4 5 1 4
加 [3,4] 2	6 6 6 7 1 4
查询 [1,4]		7
查询 [2,3]		6
赋值 [1,6] 为 -1	-1 -1 -1 -1 -1 -1
查询 [1,6]		-1

观察表中两次查询与最后的大范围赋值：位置 3 先被赋值 6、又被加 2，最终值是 8 的过程没有被单独展示，但它说明了"加在赋值之上"的复合；而最后一次赋值 [1,6] 为 -1 把前面所有加法一并覆盖，回答出全负数区间的最大值 -1。两次查询答案 7、6 分别来自不同位置的当前值，说明修改必须实时生效，这正是懒标记线段树要维护的真实信息。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-12 22:10
 * update_at: 2026-08-13 11:26
 */
#include <bits/stdc++.h>
using namespace std;

// 仿照 rbook 模板 segtree-range-assign 的 pull/apply/push 结构，
// 把「区间赋值」扩展成「区间赋值 + 区间加」双懒标记：
// 赋值标记会覆盖旧的加法标记，加法若遇到赋值标记则改写赋值标记，
// 下传时顺序固定为「先赋值、后加法」。
template <typename T>
struct SegmentTreeAssignAddMax {
    // 线段树节点：最大值 + 两个懒标记（赋值覆盖加法）。
    struct Node {
        T max;        // 区间最大值
        T add_lazy;   // 区间整体还要加多少（未下传）
        T set_lazy;   // 区间整体被赋成什么值（未下传）
        bool set_flag; // 是否有未下传的赋值标记
    };

    int n = 0;
    vector<Node> tree; // tree[p] 表示节点 p 的信息与懒标记

    SegmentTreeAssignAddMax(int n = 0) {
        init(n);
    }

    void init(int size) {
        n = size;
        tree.assign(n * 4 + 5, Node{0, 0, 0, false});
    }

    // 用两个儿子的最大值合并出父节点的最大值。
    void push_up(int p) {
        tree[p].max = std::max(tree[p << 1].max, tree[p << 1 | 1].max);
    }

    // 把节点 p 的整段区间赋值为 value：
    // 最大值直接变成 value，旧的加法标记被赋值覆盖，只留下赋值标记。
    void apply_set(int p, T value) {
        tree[p].max = value;
        tree[p].set_lazy = value;
        tree[p].add_lazy = 0;
        tree[p].set_flag = true;
    }

    // 给节点 p 的整段区间加上 value：
    // 最大值直接加 value；若已有赋值标记，等价于整体赋成 (赋值 + value)，
    // 所以改写 set_lazy；否则累加到加法标记上。
    void apply_add(int p, T value) {
        tree[p].max += value;
        if (tree[p].set_flag)
            tree[p].set_lazy += value;
        else
            tree[p].add_lazy += value;
    }

    // 下传节点 p 的懒标记：必须先传赋值、再传加法，儿子才能得到正确复合结果。
    void push_down(int p, int l, int r) {
        if (l == r) return;

        if (tree[p].set_flag) {
            apply_set(p << 1, tree[p].set_lazy);
            apply_set(p << 1 | 1, tree[p].set_lazy);
            tree[p].set_flag = false;
        }
        if (tree[p].add_lazy != 0) {
            apply_add(p << 1, tree[p].add_lazy);
            apply_add(p << 1 | 1, tree[p].add_lazy);
            tree[p].add_lazy = 0;
        }
    }

    // 用初始数组 a 建树，叶子存单点值。
    void build(const vector<T> &a, int l, int r, int p = 1) {
        if (l == r) {
            tree[p].max = a[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(a, l, mid, p << 1);
        build(a, mid + 1, r, p << 1 | 1);
        push_up(p);
    }

    // 把区间 [ql, qr] 整体赋值为 value。
    void assign_range(int ql, int qr, T value, int l, int r, int p = 1) {
        if (ql <= l && r <= qr) {
            apply_set(p, value);
            return;
        }

        push_down(p, l, r);
        int mid = (l + r) >> 1;
        if (ql <= mid) assign_range(ql, qr, value, l, mid, p << 1);
        if (qr > mid) assign_range(ql, qr, value, mid + 1, r, p << 1 | 1);
        push_up(p);
    }

    // 给区间 [ql, qr] 整体加上 value。
    void add_range(int ql, int qr, T value, int l, int r, int p = 1) {
        if (ql <= l && r <= qr) {
            apply_add(p, value);
            return;
        }

        push_down(p, l, r);
        int mid = (l + r) >> 1;
        if (ql <= mid) add_range(ql, qr, value, l, mid, p << 1);
        if (qr > mid) add_range(ql, qr, value, mid + 1, r, p << 1 | 1);
        push_up(p);
    }

    // 查询区间 [ql, qr] 的最大值。
    T query(int ql, int qr, int l, int r, int p = 1) {
        if (ql <= l && r <= qr) return tree[p].max;

        push_down(p, l, r);
        int mid = (l + r) >> 1;
        // 初值取很小的数，保证全负数区间也能正确取 max。
        T answer = -(1LL << 60);
        if (ql <= mid) answer = max(answer, query(ql, qr, l, mid, p << 1));
        if (qr > mid) answer = max(answer, query(ql, qr, mid + 1, r, p << 1 | 1));
        return answer;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<long long> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    SegmentTreeAssignAddMax<long long> seg(n);
    seg.build(a, 1, n);

    while (m--) {
        int op;
        cin >> op;
        if (op == 1) {
            int l, r;
            long long x;
            cin >> l >> r >> x;
            seg.assign_range(l, r, x, 1, n);
        } else if (op == 2) {
            int l, r;
            long long x;
            cin >> l >> r >> x;
            seg.add_range(l, r, x, 1, n);
        } else {
            int l, r;
            cin >> l >> r;
            cout << seg.query(l, r, 1, n) << '\n';
        }
    }

    return 0;
}

复杂度

时间：建树 $O(n)$ ，单次操作 $O(\log n)$ ，总 $O((n+q) \log n)$ 。
空间：线段树四倍数组（三个 long long 数组加一个位压缩布尔数组）， $O(n)$ 。

总结

区间赋值 + 区间加 + 区间最大值是"双懒标记"最标准的模板题：赋值覆盖加法、加法改写赋值标记、下传先赋值后加。理解了 apply_set / apply_add / push 的复合顺序，就掌握了多懒标记线段树的核心套路。rbook 的《线段树：区间赋值与区间查询》讲解了同一种 pull / apply / push 模板结构，本解由该模板（segtree-range-assign）把"区间和 + 赋值懒标记"扩展为"区间最大值 + 赋值/加法双懒标记"而来。

图示解析

这张 ASCII 图展示整道题的解题路线：

text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19朴素模拟（brute.cpp）
  数组 a[1..n] 逐项赋值 / 逐项加 / 逐项比最大值      O(n) 每次操作
        |
        | 瓶颈：单次操作 O(n)，q 次操作 O(n*q) 太大
        v
关键观察
  整段赋值 -> 最大值变成 x；整段加 -> 最大值加 x（摘要自同态）
  赋值覆盖加法，加法叠加到赋值上（复合顺序固定）
        |
        v
线段树 + 双懒标记（main.cpp）
  节点存区间最大值 tree
  apply_set：tree = x，set_lazy = x，清空 add_lazy
  apply_add：tree += x；有赋值标记则 set_lazy += x，否则 add_lazy += x
  push：先传赋值、再传加法；再递归进子树
  查询：整段直接返回，部分覆盖先下传再合并
        |
        v
复杂度 O((n + q) log n)，空间 O(n)

图中三条主线分别对应"暴力在哪里慢"“观察到什么性质”“正式解如何用两个懒标记实现”。核心是"赋值与加法两种整段变换的复合顺序"：它决定了 apply_set 要清空加法标记、apply_add 要改写赋值标记、push 必须先赋值后加法这三条实现规则。

目录

形式化题目

思路

数学视角：为什么懒标记能成立

代码

复杂度

总结

图示解析