多种懒标记

1 操作顺序

现在同时支持区间乘、区间加和区间求和,所有结果对正整数 MM 取模。

只分别记录“总共乘多少”和“总共加多少”,还必须规定它们的执行顺序。例如对 xx:先加 33 再乘 22 得到 2x+62x+6,先乘 22 再加 33 则得到 2x+32x+3。

先加后乘与先乘后加得到不同的常数项

2 统一表示

用二元组 (a,b)(a,b) 表示变换

f(x)=ax+b. f(x)=ax+b.
操作 对应变换
不修改 (1,0)(1,0)
加 vv (1,v)(1,v)
乘 vv (v,0)(v,0)
赋值为 vv (0,v)(0,v)

节点保存 mul[p]、inc[p],约定它们表示孩子尚未执行的变换 x↦ax+bx\mapsto ax+b。

3 复合公式

假设旧标记为 f(x)=ax+bf(x)=ax+b,后来又执行 g(x)=Ax+Bg(x)=Ax+B。孩子以后应先执行旧操作,再执行新操作,所以合成标记为

g(f(x))=A(ax+b)+B=(Aa)x+(Ab+B). g(f(x))=A(ax+b)+B=(Aa)x+(Ab+B).

因此:

mul[p] = mul[p] * A % mod;
inc[p] = (inc[p] * A % mod + B) % mod;

新的乘法不仅作用于原始元素,也作用于此前累积的加法。把第二行写成 inc[p] += B 会丢掉这部分影响。

区间长度为 lenlen、旧和为 SS 时,新和为

S′=AS+B⋅len. S'=AS+B\cdot len.

因为对每一个元素都执行 Ax+BAx+B,其中 AA 作用于整段总和,BB 要计入 lenlen 次。

4 下传

下传时,把父亲的 (a,b)(a,b) 当作新变换,分别复合到两个孩子上,然后将父标记重置为 (1,0)(1,0)。

父标记相对孩子已有的标记更晚发生:任何先前进入孩子的操作,都必须先下传当时的父标记。因此复合顺序仍是“孩子旧操作在前,父亲待下传操作在后”。

函数复合满足结合律,可以把一串操作压缩为一个标记;它通常不满足交换律,不能改变时间顺序。

区间查询先排除空交集并返回 00,完整覆盖时返回节点和;部分相交时才下传,再递归左右两个孩子,将结果相加后取模。不需要在调用前分别判断查询区间是否跨过中点。

5 赋值与加法

赋值也是同一公式的特例。

  • 旧标记之后赋值 vv:取 (A,B)=(0,v)(A,B)=(0,v),新标记变为 (0,v)(0,v),旧操作全部失效。
  • 已有赋值 vv 之后加 dd:(0,v)(0,v) 变为 (0,v+d)(0,v+d)。

因此本篇 update 也能支持区间赋值,只需传入 A=0、B=norm(v);完整程序保留乘、加、查询三种输入操作。

这套公式针对区间和。若维护最大值,乘负数会交换最大值与最小值,不能照搬区间和模板。

6 代码

输入格式对应 luogu P3373: 【模板】线段树 2:第一行 n q M,第二行初始数组;1 l r v 表示乘,2 l r v 表示加,3 l r 表示求和。

模板容量为 n≤105n\le 10^5,支持 1≤M≤109+71\le M\le 10^9+7。初值和增量可以为负,统一归一化到 [0,M−1][0,M-1]。

#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

第二次修改后数组为 [5,7,6][5,7,6];最后在模 100100 下为 [5,99,99][5,99,99],总和对 100100 取模为 33。

7 边界与复杂度

建树 O(n)O(n),单次操作 O(log⁡n)O(\log n),空间 O(n)O(n)。

乘法标记初值必须是 11,不能依赖全局数组的默认零值。代码用 1 % mod 表示单位变换,兼容 M=1M=1。所有乘积使用 long long;上述模数上界保证两个模内数相乘不会溢出。更大模数需要另行处理乘法溢出。

8 练习

9 相关题解

暂无相关题解