1 操作顺序
现在同时支持区间乘、区间加和区间求和,所有结果对正整数
只分别记录“总共乘多少”和“总共加多少”,还必须规定它们的执行顺序。例如对
2 统一表示
用二元组
| 操作 | 对应变换 |
|---|---|
| 不修改 | |
| 加 |
|
| 乘 |
|
| 赋值为 |
节点保存 mul[p]、inc[p],约定它们表示孩子尚未执行的变换
3 复合公式
假设旧标记为
因此:
mul[p] = mul[p] * A % mod;
inc[p] = (inc[p] * A % mod + B) % mod;
新的乘法不仅作用于原始元素,也作用于此前累积的加法。把第二行写成 inc[p] += B 会丢掉这部分影响。
区间长度为
因为对每一个元素都执行
4 下传
下传时,把父亲的
父标记相对孩子已有的标记更晚发生:任何先前进入孩子的操作,都必须先下传当时的父标记。因此复合顺序仍是“孩子旧操作在前,父亲待下传操作在后”。
函数复合满足结合律,可以把一串操作压缩为一个标记;它通常不满足交换律,不能改变时间顺序。
区间查询先排除空交集并返回
5 赋值与加法
赋值也是同一公式的特例。
- 旧标记之后赋值
:取 ,新标记变为 ,旧操作全部失效。 - 已有赋值
之后加 : 变为 。
因此本篇 update 也能支持区间赋值,只需传入 A=0、B=norm(v);完整程序保留乘、加、查询三种输入操作。
这套公式针对区间和。若维护最大值,乘负数会交换最大值与最小值,不能照搬区间和模板。
6 代码
输入格式对应 luogu P3373: 【模板】线段树 2:第一行 n q M,第二行初始数组;1 l r v 表示乘,2 l r v 表示加,3 l r 表示求和。
模板容量为
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int ls(int p) { return p << 1; } // 左孩子 2p
int rs(int p) { return p << 1 | 1; } // 右孩子 2p+1
const int maxn = 100000 + 5;
int n, q;
// 区间和对 mod 取模;乘积使用 ll,模板要求 mod ≤ 10^9+7。
ll mod, a[maxn], tr[maxn * 4];
// 待下传标记表示 x -> mul[p]*x + inc[p],尚未作用于孩子。
ll mul[maxn * 4], inc[maxn * 4];
// C++ 的负数取模可能为负,将外来数值统一到 [0,mod-1]。
ll norm(ll x) {
x %= mod;
if (x < 0) x += mod;
return x;
}
// 左右区间和相加后仍需取模。
void pushup(int p) {
tr[p] = (tr[ls(p)] + tr[rs(p)]) % mod;
}
// 建立节点 p 表示的 [l,r]。加法标记默认为 0,乘法标记须设为 1。
void build(int p, int l, int r) {
mul[p] = 1 % mod; // 单位变换;取模写法兼容 mod == 1
if (l == r) {
tr[p] = norm(a[l]);
return;
}
int mid = l + (r - l) / 2;
build(ls(p), l, mid);
build(rs(p), mid + 1, r);
pushup(p);
}
// 在旧变换 x -> a*x+b 之后执行 x -> A*x+B;A、B 已归一化。
// 合成结果为 x -> (A*a)*x + (A*b+B),时间顺序不能交换。
void apply(int p, int l, int r, ll A, ll B) {
tr[p] = (tr[p] * A % mod + B * (r - l + 1) % mod) % mod; // B 贡献 len 次
mul[p] = mul[p] * A % mod;
inc[p] = (inc[p] * A % mod + B) % mod; // 新乘法也会放大旧加法
}
// 进入孩子前,将父标记作为较新的变换复合到孩子,再恢复单位标记。
void pushdown(int p, int l, int r) {
if (mul[p] == 1 % mod && inc[p] == 0) return;
int mid = l + (r - l) / 2;
apply(ls(p), l, mid, mul[p], inc[p]);
apply(rs(p), mid + 1, r, mul[p], inc[p]);
mul[p] = 1 % mod;
inc[p] = 0;
}
// 对 [L,R] 中每个数执行 A*x+B;完整覆盖时不再向下递归。
void update(int p, int l, int r, int L, int R, ll A, ll B) {
if (L <= l && r <= R) {
apply(p, l, r, A, B);
return;
}
pushdown(p, l, r);
int mid = l + (r - l) / 2;
if (L <= mid) update(ls(p), l, mid, L, R, A, B);
if (R > mid) update(rs(p), mid + 1, r, L, R, A, B);
pushup(p);
}
// 不相交返回 0,完整覆盖返回节点和;部分相交才下传并合并。
ll query(int p, int l, int r, int L, int R) {
if (r < L || R < l) return 0;
if (L <= l && r <= R) return tr[p];
pushdown(p, l, r);
int mid = l + (r - l) / 2;
return (query(ls(p), l, mid, L, R)
+ query(rs(p), mid + 1, r, L, R)) % mod;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> q >> mod;
for (int i = 1; i <= n; ++i) cin >> a[i];
build(1, 1, n);
while (q--) {
int op, l, r;
cin >> op >> l >> r;
if (op == 3) {
cout << query(1, 1, n, l, r) << '\n';
} else {
ll v;
cin >> v;
// 乘 v 对应 (v,0),加 v 对应 (1,v)。
if (op == 1) update(1, 1, n, l, r, norm(v), 0);
else update(1, 1, n, l, r, 1 % mod, norm(v));
}
}
return 0;
}
输入:
3 7 100
1 2 3
1 1 3 2
2 1 2 3
3 1 3
1 2 3 0
2 2 3 -1
3 1 3
3 2 2
输出:
18
3
99
第二次修改后数组为
7 边界与复杂度
建树
乘法标记初值必须是 1 % mod 表示单位变换,兼容 long long;上述模数上界保证两个模内数相乘不会溢出。更大模数需要另行处理乘法溢出。
8 练习
- luogu P3373: 【模板】线段树 2:乘加标记复合。
- 增加
4 l r v,表示区间赋值,用同一个update实现。 - luogu P1253: 扶苏的问题:赋值、加法与最大值。重新设计节点更新规则,注意其数据规模达到
。
9 相关题解
暂无相关题解