「一本通 4.3 练习 3」维护序列

GitHub跳转原题关系图返回列表

区间乘与区间加统一为仿射变换 x→bx+c，线段树用（乘，加）双分量懒标记复合下推，O((n+m)log n) 维护区间和模 P。

OJ: roj

题目 ID: 1551

难度:提高

标签:线段树懒标记一本通python

创建: 2026-09-30 17:44

更新: 2026-10-07 11:01

形式化题目

给定长度为 $n$ 的非负整数序列 $a[1..n]$ 与模数 $P$ ，支持 $m$ 次操作（ $1 \leqslant t \leqslant g \leqslant n$ ， $0 \leqslant c \leqslant 10^9$ ）：

1 t g c：对每个 $i \in [t, g]$ ，令 $a_i \gets a_i \times c \bmod P$ ；
2 t g c：对每个 $i \in [t, g]$ ，令 $a_i \gets a_i + c$ ；
3 t g：输出 $\sum_{i=t}^{g} a_i \bmod P$ 。

以题面样例（ $P = 43$ ， $a = [1, 2, 3, 4, 5, 6, 7]$ ）逐操作推演，表格中"处理后序列"是该操作执行完后的状态：

序号	操作	处理后序列 $a$	本步输出
1	`1 2 5 5`	$[1,\ 10,\ 15,\ 20,\ 25,\ 6,\ 7]$	—
2	`3 2 4`	同上	$10 + 15 + 20 = 45$ ， $45 \bmod 43 = 2$
3	`2 3 7 9`	$[1,\ 10,\ 24,\ 29,\ 34,\ 15,\ 16]$	—
4	`3 1 3`	同上	$1 + 10 + 24 = 35$
5	`3 4 7`	同上	$29 + 34 + 15 + 16 = 94$ ， $94 \bmod 43 = 8$

三次询问依次输出 $2$ 、 $35$ 、 $8$ 。注意题面【提示】把第 2 次询问写成 22，但 $45 \bmod 43 = 2$ ，与【输出样例】一致，以样例输出为准（题面笔误）。

正解

思路

1. 朴素做法与其瓶颈

每次修改、询问都逐点扫完整个 $[t, g]$ ：单次 $O(n)$ ，总计 $O(nm) = 10^{10}$ ，超时。

把查询侧直接换成经典的"区间和 + 懒标记"线段树只救一半：那种线段树只有加法标记。遇到区间乘时，段内每个数从 $x + a$ 变成 $b(x + a) = bx + ba$ ，不再是"加一个常数"——加法标记家族对乘法不封闭；反过来乘法标记也接不住加法（ $bx + c$ 不是"乘一个常数"）。两种标记各存各的，下推时还得分谁先谁后。瓶颈是：要找一个对乘、加都封闭的标记结构。

2. 关键观察：修改都是仿射变换，且复合封闭

把每个修改看成对段内每个数施加的变换 $x \mapsto b \cdot x + c \pmod P$ ：

操作	变换 $(b, c)$
区间乘 $v$	$(v \bmod P,\ 0)$
区间加 $v$	$(1,\ v \bmod P)$

仿射变换按"先做已有标记 $(m, a)$ （即孩子还欠着的变换），再做新操作 $(b, c)$ "复合：

x \xrightarrow{\ (m, a)\ } mx + a \xrightarrow{\ (b, c)\ } b(mx + a) + c = (bm)\,x + (ba + c)

复合结果 $(bm,\ ba + c)$ 仍是仿射变换，恒等变换 $(1, 0)$ 是单位元——封闭性正是第 1 节里加法标记缺失的性质，于是乘和加共用同一个标记，不再需要区分先后。

区间和在变换下的像也有闭式：长度 $L$ 、当前和 $S$ 的整段套用 $(b, c)$ 后变成

S \mapsto bS + cL \pmod P

所以整段结算不需要知道段内每个数是什么。

3. 线段树设计

线段树每个节点存区间和 $t$ 与懒标记 $(m, a)$ ，三个核心动作：

apply(node, L, b, c)：整段结算 $t \gets bt + cL$ ，并把标记复合为 $(bm,\ ba + c)$ ；
push(node)：把本节点标记对两个孩子 apply（孩子的真实和被一并修正），本节点复位为 $(1, 0)$ ；
update / query：查询区间整段覆盖直接返回 $t$ ，修改整段覆盖直接 apply；否则先 push 兑现欠账，只递归真正相交的一侧，回溯时用两个孩子的和刷新 $t$ 。

区间分解的 $O(\log n)$ 来源如下图（规模 7 的线段树，节点标注其代表的区间）：

任意操作区间都被拆成 $O(\log n)$ 个"整段节点"：例如修改 $[2, 5]$ 命中 [2,2]、[3,4]、[5,5] 三个整段，各花 $O(1)$ 结算，不必访问区间内的每个点。

正确性依赖一条不变式：节点的 $t$ 恒等于其真实区间和模 $P$ （因而恒小于 $P$ ），标记恒等于孩子欠做的变换。整段修改只更新自己、把欠账复合进标记；任何要读孩子的地方都先 push 兑现欠账——沿递归深度归纳，每次读到的 $t$ 都是真实值。

代码

Python 版：

python

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#!/usr/bin/env python3
# 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-09-30 17:44
# update_at: 2026-09-30 17:52

import sys

# 懒标记下标：节点挂着的待做变换是"整段先乘 z[MUL] 再加 z[ADD]"，恒等变换为 (1, 0)
MUL, ADD = 0, 1
IDLE = [1, 0]  # 恒等标记：乘 1 加 0，什么都不做


def apply(node: int, ln: int, b: int, c: int, p: int, t: list[int], z: list[list[int]]) -> None:
    """把变换 x -> b*x+c 整段作用到节点：刷新区间和，并把新变换复合进原标记。

    原标记表示孩子还需做 x -> m*x+a；先做它再做新变换复合出
    x -> b*(m*x+a)+c = (b*m)*x + (b*a+c)，因此标记只增不减、始终等价于整段的累计变换。
    """
    t[node] = (b * t[node] + c * ln) % p
    old = z[node]
    z[node] = [old[MUL] * b % p, (old[ADD] * b + c) % p]


def push(node: int, lo: int, hi: int, p: int, t: list[int], z: list[list[int]]) -> None:
    """把本节点的累计变换下推给两个孩子，再把本节点标记还原为恒等。

    只在"未被查询区间整段覆盖"时才会走到这里，此时必有 lo < hi，孩子一定存在。
    """
    b, c = z[node]
    if b == 1 and c == 0:  # 没有挂标记，省掉一次复合
        return
    mid = (lo + hi) >> 1
    apply(node << 1, mid - lo + 1, b, c, p, t, z)
    apply(node << 1 | 1, hi - mid, b, c, p, t, z)
    z[node] = IDLE


def build(node: int, lo: int, hi: int, arr: list[int], t: list[int], p: int) -> None:
    """建树：叶子存单个数，父节点存两个孩子的和（同样取模，保证 t 恒小于 p）。"""
    if lo == hi:
        t[node] = arr[lo - 1]
        return
    mid = (lo + hi) >> 1
    build(node << 1, lo, mid, arr, t, p)
    build(node << 1 | 1, mid + 1, hi, arr, t, p)
    t[node] = (t[node << 1] + t[node << 1 | 1]) % p


def update(node: int, lo: int, hi: int, ql: int, qr: int,
           b: int, c: int, p: int, t: list[int], z: list[list[int]]) -> None:
    """区间套用变换 x -> b*x+c：整段落入就地作用，否则下推后递归两侧并上收区间和。"""
    if ql <= lo and hi <= qr:
        apply(node, hi - lo + 1, b, c, p, t, z)
        return
    push(node, lo, hi, p, t, z)
    mid = (lo + hi) >> 1
    if ql <= mid:  # 只下探真正相交的一侧
        update(node << 1, lo, mid, ql, qr, b, c, p, t, z)
    if qr > mid:
        update(node << 1 | 1, mid + 1, hi, ql, qr, b, c, p, t, z)
    t[node] = (t[node << 1] + t[node << 1 | 1]) % p


def query(node: int, lo: int, hi: int, ql: int, qr: int,
          p: int, t: list[int], z: list[list[int]]) -> int:
    """区间求和模 p：整段落入直接返回，否则下推标记后累加相交两侧。"""
    if ql <= lo and hi <= qr:
        return t[node]
    push(node, lo, hi, p, t, z)
    mid = (lo + hi) >> 1
    total = 0
    if ql <= mid:
        total = query(node << 1, lo, mid, ql, qr, p, t, z)
    if qr > mid:
        total += query(node << 1 | 1, mid + 1, hi, ql, qr, p, t, z)
    return total % p


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, p = next(data), next(data)
    arr = [next(data) % p for _ in range(n)]  # 初始数列先取模，后续所有量都留在模 p 意义下
    t = [0] * (n << 2)                        # 区间和
    z = [list(IDLE) for _ in range(n << 2)]   # 每节点独立一份标记，不能共享同一列表
    build(1, 1, n, arr, t, p)

    out: list[str] = []
    m = next(data)
    for _ in range(m):
        op = next(data)
        l, r = next(data), next(data)
        if op == 3:  # 询问 l..r 的和模 p
            out.append(str(query(1, 1, n, l, r, p, t, z)))
            continue
        c = next(data) % p
        # 操作 1 = 变换 x -> c*x；操作 2 = 变换 x -> x + c
        update(1, 1, n, l, r, c if op == 1 else 1, 0 if op == 1 else c, p, t, z)

    print('\n'.join(out))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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/**
 * 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-10-05 07:44
 * update_at: 2026-10-05 07:44
 */
#include <iostream>
using namespace std;

typedef long long ll;

const int MAXN = 100005;

ll n, mod;
ll a[MAXN];             // 初始数列 a[1..n]
ll sumv[MAXN << 2];     // 线段树节点维护的区间和（恒小于 mod）
ll mulv[MAXN << 2];     // 懒标记的乘分量：孩子还欠着的变换是 x -> mulv*x
ll addv[MAXN << 2];     // 懒标记的加分量：孩子还欠着的变换是 x -> mulv*x+addv

// 把仿射变换 x -> b*x+c 整段作用到节点 node（对应区间长度 ln）。
// 原标记 (mulv, addv) 表示先做它再做新变换，复合为 (mulv*b, addv*b+c)。
void apply_node(ll node, ll ln, ll b, ll c) {
    sumv[node] = (b * sumv[node] + c * ln) % mod;
    mulv[node] = mulv[node] * b % mod;
    addv[node] = (addv[node] * b + c) % mod;
}

// 把节点 node 的懒标记下推给孩子，随后本节点标记复位为恒等变换 (1, 0)。
// 只有未被操作区间整段覆盖时才会下推，此时必有 lo < hi，两个孩子一定存在。
void push_down(ll node, ll lo, ll hi) {
    if (mulv[node] == 1 && addv[node] == 0) return;
    ll mid = (lo + hi) >> 1;
    apply_node(node << 1, mid - lo + 1, mulv[node], addv[node]);
    apply_node(node << 1 | 1, hi - mid, mulv[node], addv[node]);
    mulv[node] = 1;
    addv[node] = 0;
}

// 建树：叶子存单个数，父节点存两个孩子和再对 mod 取模。
void build(ll node, ll lo, ll hi) {
    mulv[node] = 1;
    addv[node] = 0;
    if (lo == hi) {
        sumv[node] = a[lo] % mod;
        return;
    }
    ll mid = (lo + hi) >> 1;
    build(node << 1, lo, mid);
    build(node << 1 | 1, mid + 1, hi);
    sumv[node] = (sumv[node << 1] + sumv[node << 1 | 1]) % mod;
}

// 区间 [ql, qr] 整段套用变换 x -> b*x+c。
void update(ll node, ll lo, ll hi, ll ql, ll qr, ll b, ll c) {
    if (ql <= lo && hi <= qr) {
        apply_node(node, hi - lo + 1, b, c);
        return;
    }
    push_down(node, lo, hi);
    ll mid = (lo + hi) >> 1;
    if (ql <= mid) update(node << 1, lo, mid, ql, qr, b, c);
    if (qr > mid) update(node << 1 | 1, mid + 1, hi, ql, qr, b, c);
    sumv[node] = (sumv[node << 1] + sumv[node << 1 | 1]) % mod;
}

// 查询区间 [ql, qr] 的和模 mod。
ll query(ll node, ll lo, ll hi, ll ql, ll qr) {
    if (ql <= lo && hi <= qr) return sumv[node];
    push_down(node, lo, hi);
    ll mid = (lo + hi) >> 1;
    ll total = 0;
    if (ql <= mid) total = query(node << 1, lo, mid, ql, qr);
    if (qr > mid) total += query(node << 1 | 1, mid + 1, hi, ql, qr);
    return total % mod;
}

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

    cin >> n >> mod;
    for (ll i = 1; i <= n; i++) {
        cin >> a[i];
    }
    build(1, 1, n);

    ll m;
    cin >> m;
    for (ll i = 1; i <= m; i++) {
        ll op, l, r, c;
        cin >> op >> l >> r;
        if (op == 3) {
            cout << query(1, 1, n, l, r) << "\n";
            continue;
        }
        cin >> c;
        c %= mod;
        // 操作 1 是变换 x -> c*x；操作 2 是变换 x -> x+c。
        if (op == 1) {
            update(1, 1, n, l, r, c, 0);
        } else {
            update(1, 1, n, l, r, 1, c);
        }
    }

    return 0;
}

复杂度

时间复杂度：建树 $O(n)$ ；每次操作把区间拆成 $O(\log n)$ 个整段节点，递归路径也是 $O(\log n)$ ，每个节点的 apply/读取为 $O(1)$ 。合计 $O((n + m) \log n)$ ，与 C++ 双标记正解同阶。
空间复杂度：线段树 $4n$ 个节点各存一个和与一个二元标记，输出列表 $O(m)$ ，合计 $O(n + m)$ ；本实现峰值约 92MB。

总结

区间乘、区间加单独看都是简单懒标记，难在两者混合：标记结构必须对两种操作都封闭，而加法标记扛不住乘法（ $(x + a)b = bx + ba$ 不再是加法）。把两类操作统一成仿射变换 $x \mapsto bx + c$ 后，封闭性由复合律

(m, a) \circ (b, c) = (bm,\ ba + c)

直接给出：乘、加共用一个 $(m, a)$ 双分量标记，apply 负责"整段结算 $bS + cL$ + 标记复合"，push 负责下推兑现， $O((n + m) \log n)$ 完成全部操作。实现上最容易写反的是复合次序——新操作最后作用在数上，标记应取 $(bm,\ ba + c)$ ；若写成 $(bm,\ mc + a)$ 就把先后顺序颠倒了：以样例为例，节点 [3,4] 先被乘 5、再被加 9，正确标记是 $(5, 9)$ ，颠倒后是 $(5, 5)$ ，随后的询问 3 1 3 会把 $a_3$ 算成 20 而不是 24，立刻暴露。

【题目描述】

原题来自：AHOI 2009

老师交给小可可一个维护数列的任务，现在小可可希望你来帮他完成。

有长为 $n$ 的数列，不妨设为 $a\_1,a\_2,\\cdots ,a\_n$ 。有如下三种操作形式：

把数列中的一段数全部乘一个值；

把数列中的一段数全部加一个值；

询问数列中的一段数的和，由于答案可能很大，你只需输出这个数模 $P$ 的值。

【输入】

第一行两个整数 $n$ 和 $P$ ；

第二行含有 $n$ 个非负整数，从左到右依次为 $a\_1,a\_2,\\cdots ,a\_n$ ；

第三行有一个整数 $M$ ，表示操作总数；

从第四行开始每行描述一个操作，输入的操作有以下三种形式：

操作 $1：1\\ t\\ g\\ c$ ，表示把所有满足 $t≤i≤g$ 的 $a\_i$ 改为 $a\_i×c$ ；

操作 $2：2\\ t\\ g\\ c$ ，表示把所有满足 $t≤i≤g$ 的 $a\_i$ 改为 $a\_i+c$ ；

操作 $3：3\\ t\\ g$ ，询问所有满足 $t≤i≤g$ 的 $a\_i$ 的和模 $P$ 的值。

同一行相邻两数之间用一个空格隔开，每行开头和末尾没有多余空格。

【输出】

对每个操作 $3$ ，按照它在输入中出现的顺序，依次输出一行一个整数表示询问结果。

【输入样例】

text

1
2
3
4
5
6
7
87 43
1 2 3 4 5 6 7
5
1 2 5 5
3 2 4
2 3 7 9
3 1 3
3 4 7

【输出样例】

text

【提示】

样例说明:

初始时数列为 $\\{1,2,3,4,5,6,7\\}$ ；

经过第 $1$ 次操作后，数列为 $\\{1,10,15,20,25,6,7\\}$ ；

对第 $2$ 次操作，和为 $10+15+20=45$ ，模 $43$ 的结果是 22；

经过第 $3$ 次操作后，数列为 $\\{1,10,24,29,34,15,16\\}$ ；

对第 $4$ 次操作，和为 $1+10+24=35$ ，模 $43$ 的结果是 $35$ ；

对第 $5$ 次操作，和为 $29+34+15+16=94$ ，模 $43$ 的结果是 $8$ 。

数据范围与提示：

对于全部测试数据， $1≤t≤g≤n,0≤c,a\_i≤10^9 ,1≤P≤10^9$ 。

测试数据规模如下表所示：

数据编号

$1$

$2,3$

$4$

$5$

$6$

$7$

$8$

$9,10$

$n=$

$10$

$10^3$

$10^4$

$6×10^4$

$7×10^4$

$8×10^4$

$9×10^4$

$10^5$

$M=$