对做算法题的朋友来说，看到“维护序列”这四个字，应该心里就有数了。这道题在信息学奥赛一本通里是P1551，在洛谷上是P2023，题目一模一样，都是经典的线段树模板题，但绝不是那种五分钟就能写过去的入门题。它最大的价值在于：强迫你真正理解懒标记的运作机制，尤其是当区间上同时存在加法和乘法两种操作时，标记之间的优先级、合并顺序、下传时机，任何一个细节写错，结果就是一片红。
这篇内容我按自己的理解重新捋一遍，把这道题从题目分析、思路推导、完整代码到踩坑记录全部拆开讲清楚。适合已经会写基础线段树、想进阶搞懂双懒标记的朋友，也适合正在备战NOIP、CSP-J/S、蓝桥杯等竞赛、被这道题卡住的同学直接参考。我会把每一步为什么这么做讲明白，而不是给你一份能过样例就完事的代码。
1. 题目分析与核心思路拆解
1.1 题目到底在问什么
先看看题面。给定一个长度为n的序列，你需要支持三种操作：
- 区间加法：把[l, r]区间内每个数加上一个值k
- 区间乘法：把[l, r]区间内每个数乘上一个值k
- 区间求和：查询[l, r]区间内所有数的和对某个模数p取模后的结果
n和操作次数m的数据范围通常在10^5级别，这意味着暴力修改、暴力查询是肯定过不去的。你的单次操作必须做到O(log n)，除了线段树或者树状数组这类数据结构，没有别的选择。
而树状数组虽然也能支持区间修改、区间查询，但它是通过差分思想间接实现的。在这道题里，加法之后还要乘法、乘法之后还要加法，两种操作交替进行，树状数组处理起来非常别扭——你需要维护的东西会变得极其复杂，稍有不慎就差之千里。所以，这道题的标准解法就是线段树，而且是带懒标记的线段树。
我第一次见到这个题是在一本通上，当时自认为线段树写得很熟练了，结果一上手就发现不对劲：加法好写，乘法也好写，但两个合在一起，懒标记怎么存、怎么下传，彻底懵了。这个“懵”的过程，恰恰就是这道题真正想教给你的东西。
1.2 为什么说这是一道“卡住无数人”的进阶题
如果你只写过单点修改、区间求和的线段树，那懒标记对你来说只是一个简单的“暂存”概念：某个节点代表的整个区间被整体修改时，我不递归到叶子，而是把修改信息存在这个节点上，等下次需要下钻时再传递给子节点。
但在“维护序列”这道题里，不只有一种修改，而是两种性质不同的修改叠加在一起。问题马上就来了，举个例子：
假设某个区间节点上已经有一个“加5”的标记，现在又来了一个“乘3”的操作。那么这个节点应该存成什么？是“先加5再乘3”，还是“先乘3再加5”？因为这会影响最终结果。更麻烦的是，如果等下又要下传，这个合并后的标记应该怎么拆分给左右孩子？
如果这两个标记是分开独立的，你根本没法确定它们之间谁先谁后。这就是这道题的核心难点——懒标记不是“存一个数”那么简单，你得设计出一套规则，让两个标记能在同一个节点上共存，并且能正确合并、正确下传。
2. 懒标记的本质：加法与乘法的优先级博弈
2.1 为什么不能简单存两个标记就完事
很多人一开始的想法是：我开两个数组，add[k]存加法标记，mul[k]存乘法标记，各自维护各自的，不就行了吗？
这个思路看着对，实际上有一个致命bug。你想想，对一个区间做“乘3”操作时，这个区间之前可能已经被“加5”了。如果我只把mul标记乘3，add标记不动，那这个区间的真实值是(old_sum + 5) * 3，还是 old_sum * 3 + 5？
正确答案取决于我们事先规定的操作顺序。但问题是，新来的操作是在旧操作之后发生的，它只能往后叠加，不能改变已经发生的顺序。
所以，单纯存两个独立的标记是不够的，你必须固定一个约定：当标记同时存在时，先做乘法，再做加法。换句话说，每个节点的真实值 = 子节点值 × mul + add。这个约定一旦定下来，所有标记的合并规则都要围绕它展开。
2.2 核心设计：乘法优先规则
我们规定，任意时刻，一个节点上记录的懒标记含义是：这个区间内的每个数，都要先乘上mul，再加上add。
基于这个规定，可以推导出两种操作的标记合并方式：
区间乘法操作：让区间内每个数乘上k。那么原来的“先乘mul再加add”就变成“先乘mul再乘以k，再加add”——乘法标记mul变成mul * k，加法标记add保持不变。
区间加法操作：让区间内每个数加上k。那么“先乘mul再加add”后面再追加一个“加k”，就变成“先乘mul，再加(add + k)”——加法标记add变成add + k，乘法标记mul保持不变。
这个逻辑一定要自己推一遍，不能死记。因为当你给一个区间做乘法时，区间内已有的加法标记也在乘法的作用范围内，但标记本身并不需要跟着乘——不对，等等，这里我刚才说错了，需要再细说。
实际上，仔细推：假设某个叶子节点的值是x，它收到的懒标记是先乘mul再加add，所以真实值是x * mul + add。现在对区间乘k，真实值变成(x * mul + add) * k = x * (mul * k) + add * k。所以乘法标记mul要乘k，加法标记add也要乘k！
也就是说：做区间乘法操作时，不仅是mul标记要乘以k，add标记也要同步乘以k。这一点极其容易漏，也是这道题最常见的WA原因之一。而做区间加法时，只需要add加k就行，mul不动。
再强调一遍，用数学式子表达：对于一个值为val的节点，打上标记(mul, add)后，其真实值 = val * mul + add。如果再来乘k的操作，新标记为(mulk, addk)；如果再来加k的操作，新标记为(mul, add+k)。
2.3 标记下传：pushdown的完整逻辑
当我们需要递归进入某个节点的子节点时，如果当前节点带有懒标记，必须先把标记下传，否则子节点的数据就是过期的。
下传的核心依据同样是“乘法优先”规则。假设当前节点有标记(mul, add)，它的左右孩子之前可能已经各自带有标记。我们需要把这份标记“叠加”到孩子身上。
对于左孩子，假设它原来的标记是(lmul, ladd)，它原来的真实值 = val * lmul + ladd。现在父节点的操作要应用在这个真实值上，变成： (val * lmul + ladd) * mul + add = val * (lmul * mul) + (ladd * mul + add)
所以，孩子的新标记是：
- 乘法标记 = lmul * mul
- 加法标记 = ladd * mul + add
这跟上面说的“乘法操作更新标记”本质上是同一个式子。也就是说，pushdown其实就是把父节点的标记当作一次“乘法+加法复合操作”，应用在孩子身上。这么想就统一了。
3. 完整实现与关键代码解读
3.1 数据结构定义与建树
这里我们使用C++实现。先定义线段树节点需要维护的信息。
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 100005; int n, m; ll p; // 模数 ll a[MAXN]; struct Node { ll sum; // 区间和(已取模) ll mul; // 乘法懒标记 ll add; // 加法懒标记 } tree[MAXN << 2];这里有个细节：sum、mul、add全部用long long。原因很简单，乘法操作中两个10^9级别的数相乘，轻松超过int范围。哪怕最终会取模，中间过程的乘法也必须在long long下进行，否则溢出后取模就全错了。这是这道题最容易出问题的地方之一。
然后建树。和普通线段树一样，递归到叶子时把原数组的值放进去，乘法标记初始化为1，加法标记初始化为0。
void build(int node, int l, int r) { tree[node].mul = 1; tree[node].add = 0; if (l == r) { tree[node].sum = a[l] % p; return; } int mid = (l + r) >> 1; build(node << 1, l, mid); build(node << 1 | 1, mid + 1, r); tree[node].sum = (tree[node << 1].sum + tree[node << 1 | 1].sum) % p; }注意乘法标记初始化为1而不是0，这是很多新手容易犯的第一个错误。乘法标记的初始值必须是乘法的单位元，也就是1。如果初始为0，任何区间一建好就整体变成0了，那还维护个啥。
3.2 核心函数：更新节点、下传标记、区间修改
接下来是三个关键函数：apply（给节点打标记）、pushdown（下传标记）、update（区间修改）。
apply函数的作用是：把一个节点代表的整个区间，应用一次“乘k加b”的复合操作。这里k是乘法系数，b是加法增量。
void apply(int node, int l, int r, ll k, ll b) { // 当前区间每个数先乘k再加b // sum = sum * k + b * len tree[node].sum = (tree[node].sum * k + b * (r - l + 1)) % p; // 更新乘法标记 tree[node].mul = (tree[node].mul * k) % p; // 更新加法标记 tree[node].add = (tree[node].add * k + b) % p; }这个函数非常重要。可以看到，当执行一次区间乘法时，调用apply(node, l, r, k, 0)；执行一次区间加法时，调用apply(node, l, r, 1, b)。通过传参统一成一个函数，代码整洁，也方便理解。
为什么sum的更新是sum * k + b * 区间长度？因为sum是区间内所有数的和，每个数都要先乘k再加b，所以总和就是原来的和乘k，再加上区间内每个数都加的b乘以个数。
pushdown函数的作用是把当前节点的标记传递给左右孩子：
void pushdown(int node, int l, int r) { if (tree[node].mul == 1 && tree[node].add == 0) return; int mid = (l + r) >> 1; apply(node << 1, l, mid, tree[node].mul, tree[node].add); apply(node << 1 | 1, mid + 1, r, tree[node].mul, tree[node].add); // 标记清零 tree[node].mul = 1; tree[node].add = 0; }这里应用了第一节推导的结论：下传标记时，孩子节点的操作序列就是“先乘父节点的mul，再加父节点的add”。通过apply函数，把这个复合操作“叠加”到孩子节点上。
区间修改函数，支持乘法和加法两种操作。用一个type参数区分，或者直接传k和b：
void update(int node, int l, int r, int L, int R, ll k, ll b) { if (L <= l && r <= R) { apply(node, l, r, k, b); return; } pushdown(node, l, r); int mid = (l + r) >> 1; if (L <= mid) update(node << 1, l, mid, L, R, k, b); if (R > mid) update(node << 1 | 1, mid + 1, r, L, R, k, b); tree[node].sum = (tree[node].sum + tree[node << 1 | 1].sum) % p; }注意，每次递归进入子节点前必须先pushdown，否则子节点维护的sum可能是过期的，而且懒标记也没有传递下去。递归回来之后要重新计算父节点的sum，保证父节点数据同步。这两个都是线段树的基本功，但配合双懒标记时尤其要注意——pushdown里忘记清空标记，或者回溯时忘了更新父节点sum，都会造成神秘错误。
3.3 区间查询与取模细节
查询函数和普通线段树类似，只是在返回时需要把左右子树的查询结果加起来取模：
ll query(int node, int l, int r, int L, int R) { if (L <= l && r <= R) { return tree[node].sum; } pushdown(node, l, r); int mid = (l + r) >> 1; ll res = 0; if (L <= mid) res = (res + query(node << 1, l, mid, L, R)) % p; if (R > mid) res = (res + query(node << 1 | 1, mid + 1, r, L, R)) % p; return res; }关于取模，有两点心得：
第一，题目给定的模数p不一定是质数，也不一定是10^9+7这种大质数。这意味着你不能依赖任何逆元相关的操作，老老实实每次运算都取模就行。
第二，取模不要过度。有些人担心溢出，每一步都模一次，这没问题。但我自己习惯是：加法取一次，乘法取一次，乘加混合时先乘后加再取。只要数值上保证不超过long long的范围（约9.2×10^18），中间少模一次也无所谓。比如sum * k时，sum最大是p-1（10^9级别），k最大也是10^9级别，乘积是10^18级别，还在long long范围内。但如果k本身可能更大，就需要提前取模。
3.4 主函数与输入输出处理
主函数负责处理三种操作。这道题在洛谷P2023上的输入格式是：第一行n和p，第二行n个数，第三行m，接下来m行表示操作。操作格式如下：
- 操作1：1 l r k，表示区间[l, r]每个数乘k
- 操作2：2 l r k，表示区间[l, r]每个数加k
- 操作3：3 l r，查询区间[l, r]的和模p
int main() { scanf("%d%lld", &n, &p); for (int i = 1; i <= n; i++) scanf("%lld", &a[i]); build(1, 1, n); scanf("%d", &m); while (m--) { int op, l, r; ll k; scanf("%d%d%d", &op, &l, &r); if (op == 1) { scanf("%lld", &k); update(1, 1, n, l, r, k % p, 0); } else if (op == 2) { scanf("%lld", &k); update(1, 1, n, l, r, 1, k % p); } else { printf("%lld\n", query(1, 1, n, l, r) % p); } } return 0; }这里有一个小操作我很喜欢：乘法操作调用update时传k和0，加法操作传1和k。这样底层只写一个update函数，不用区分操作类型，代码量直接少了一截。
还有，输入时k要取模。虽然不取模在单次运算中也不会溢出，但万一k特别大呢？保险起见还是取一下。在比赛中，凡是能提前取模的，我都会先取掉，省得后面出问题。
4. 踩坑实录与常见问题排查
4.1 乘法标记忘记同步更新加法标记
这是我当时卡得最久的一个bug。好几天都没想明白，明明逻辑看起来没问题，怎么一乘一加结果就错了。
后来单步调试才发现，区间乘法操作时，我只更新了mul标记，add标记原封不动。按照第一节推导的规则，乘法操作是整体作用在区间每个数上的，已经存在的add标记也要被乘上k。忘记这步，等于说区间内先加的5没有被乘到3，后面查询时结果自然就少了。
怎么避免？我后来习惯把所有更新都收敛到apply函数里，统一处理sum、mul、add三个字段。只要apply函数本身是对的，所有操作都走这一条路，不会出现某个标记漏更新的情况。这也是把代码写简洁的好处之一。
4.2 取模时机不对导致溢出
新手时期我写过这样的代码：
tree[node].sum = tree[node].sum * k % p + b * (r - l + 1) % p;当时看着挺合理，每个乘法和加法都取模了。但实际运行起来，b * (r - l + 1)这段，如果b是10^9级别的数，区间长度也是10^5级别，乘积是10^14，这还在long long范围内。但问题是，如果后面再接一个加法或者乘法，就很容易爆。
正确的姿势是每一步都保证在long long能安全表示的范围，并且最终结果取模。我一般写成：
tree[node].sum = (tree[node].sum * k % p + b * (r - l + 1) % p) % p;这看起来稍微繁琐，但安全第一。尤其比赛的时候，代码能用就不要再冒险优化。
4.3 pushdown之后忘记清空父节点标记
pushdown的职责是把父节点的懒标记下传给子节点，然后父节点的标记就应该恢复成单位状态：mul = 1, add = 0。如果不恢复，下一次再对这个节点做修改时，会把这个已经过期、下传过一次的标记再次应用，结果就是重复计算。
这个bug非常隐蔽，因为如果你的查询恰好每次都递归到完整覆盖的节点，没有触发下传，结果反而是对的。只有当你需要继续往下钻时，才会出现莫名其妙的偏差。我排查这个问题时，靠的是小数据对拍：构造一个长度为5的随机序列，随机操作1000次，把线段树的结果和暴力模拟的结果对比，很快就能定位到哪些区间出错了。
4.4 递归边界和区间分裂判断
最后一个常见问题是update和query里的区间判断。
if (L <= mid) update(node << 1, l, mid, L, R, k, b); if (R > mid) update(node << 1 | 1, mid + 1, r, L, R, k, b);注意这里两个if不是互斥的，而是都要判断。因为查询或修改区间可能同时覆盖左右两半。很多新手会写成else if，结果区间恰好跨越中点时就只更新了一半，数据自然错得一塌糊涂。这个细节虽然基础，但真的大有人在错。
顺便提一句，如果你用的是洛谷网页版提交，记得选对C++标准。C++14或C++17都行，这个题不涉及复杂的语言特性，用哪个都不会出问题。有些同学在洛谷上提交是C++，在一本通OJ上提交要选C++，不要选成C语言，否则有些地方编译不过。
5. 从P1551到P2023：这道题还能怎么考
5.1 两个OJ上的题目差异
一本通P1551和洛谷P2023题面几乎完全一样，数据范围也差不多，区别主要在评测环境。一本通的数据稍温和，洛谷的数据更刁钻一些，边界情况更多。但核心算法完全一致，你在一本通上写对后，洛谷也基本能过。
不过洛谷的题面里有几个坑要注意：输入格式中模数p是负数吗？有些版本的题目p可能是负数或零，虽然实际数据不会这样，但为了稳妥，可以在读取p后做一次p = abs(p)处理。还有，询问和修改的区间l和r可能l>r，虽然一般数据不会出现，但判一下没坏处。我习惯在main函数里判断一下，如果l>r就swap，顺手的事情，省得报错后傻眼。
5.2 双懒标记的常见变式
“维护序列”这套双懒标记思想，在竞赛中衍生出很多变题：
区间赋值 + 区间加法：类似的问题，但赋值操作的优先级高于加法还是低于加法？这道题的变体在洛谷也有，例如P3373的兄弟题。核心就是重新定义标记合并规则。
区间开方 + 区间加法：这种题一般利用开方几次后数值收敛的性质，判断是否需要递归到叶子，懒标记的用法又不一样。
区间取反 + 区间翻转：这个通常是线段树维护区间信息时，通过交换左右儿子之类的操作实现，懒标记记录翻转次数即可。
掌握了双懒标记的合并原理之后，遇到这些变题你会觉得得心应手。因为本质上你学的不是一个模板，而是一种“如何用标记描述操作组合”的思维方式。
5.3 对后续算法学习的影响
说实话，这道题刷完之后，我对线段树的理解上了一个档次。以前写线段树，都是照着模板改改就上，从来没有真正理解过“懒标记到底是什么”——它本质上是操作的延迟应用，是一个可以叠加、可以合并、可以下传的复合操作的表示。
想通这一点之后，后面学线段树合并、李超线段树、可持久化线段树都顺了很多。因为那些东西的底层也是类似的“节点信息 + 标记传播”结构。只不过标记从简单的乘法加法，变成了“最大值合并”、“几何直线合并”这些更复杂的东西。
如果你正在备赛，强烈建议这道题不要直接看题解，先自己写一版，然后对拍验证。哪怕写挂了，反复调试过程中你对线段树标记机制的理解，会比刷十道简单模板题都深刻。我当年花了一个晚上在这个题上，从满盘WA到AC的那一刻，整个人是通透的。
最后再分享一个个人习惯：线段树的题，我写完不是直接提交，而是先跑一组小规模随机数据对拍，确认输出和暴力模拟一致再交。这个习惯帮我避过了不知道多少次因为边界、取模、标记顺序导致的WA。你也不妨试试。
