宝藏 - 题目列表

宝藏

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

用根号分块维护每块的未匹配删除和存活插入序列，以分块栈快速拼接双端队列并计算矩阵乘积。

OJ: shumeng

题目 ID: CSP202312D

难度:提高+/省选-

标签:根号分块数据结构矩阵乘法双端队列

日期: 2026-07-31 16:21

形式化题目

有 $n$ 条指令，每条是对矩阵双端队列的操作：在头部插入一个 $2\times2$ 矩阵、在尾部插入，或删除队列中最晚插入的矩阵。支持单点修改指令，并查询：对空队列依次执行区间 $[l,r]$ 的指令后，把队列中矩阵从头到尾相乘（元素对 $998244353$ 取模）得到的结果；队列为空时结果为单位矩阵。

思路

先看直接按区间模拟双端队列的暴力程序，它用链表记录每个插入元素的位置，删除时删掉最近插入的那个：

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/**
 * 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-07-31 16:21
 * update_at: 2026-08-17 22:40
 */
// brute.cpp：小数据暴力解，直接用链表模拟区间内的双端队列。
#include <bits/stdc++.h>
using namespace std;

const long long MOD = 998244353;

struct Matrix {
    long long a[2][2];
};

struct Operation {
    int type;
    Matrix matrix;
};

Matrix identity_matrix() {
    Matrix result = {{{1, 0}, {0, 1}}};
    return result;
}

Matrix multiply(const Matrix &left, const Matrix &right) {
    Matrix result = {};
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            for (int k = 0; k < 2; k++) {
                result.a[i][j] = (result.a[i][j] + left.a[i][k] * right.a[k][j]) % MOD;
            }
        }
    }
    return result;
}

Operation read_operation() {
    Operation result;
    cin >> result.type;
    if (result.type == 1 || result.type == 2) {
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) cin >> result.matrix.a[i][j];
        }
    }
    return result;
}

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

    int n, event_count;
    cin >> n >> event_count;
    vector<Operation> operation(n);
    for (int i = 0; i < n; i++) operation[i] = read_operation();

    while (event_count--) {
        int event_type;
        cin >> event_type;
        if (event_type == 1) {
            int index;
            cin >> index;
            operation[index - 1] = read_operation();
            continue;
        }

        int left, right;
        cin >> left >> right;
        list<Matrix> queue;
        vector<list<Matrix>::iterator> inserted;
        for (int i = left - 1; i < right; i++) {
            if (operation[i].type == 1) {
                queue.push_front(operation[i].matrix);
                inserted.push_back(queue.begin());
            } else if (operation[i].type == 2) {
                queue.push_back(operation[i].matrix);
                list<Matrix>::iterator position = queue.end();
                --position;
                inserted.push_back(position);
            } else if (!inserted.empty()) {
                queue.erase(inserted.back());
                inserted.pop_back();
            }
        }

        Matrix answer = identity_matrix();
        for (list<Matrix>::iterator it = queue.begin(); it != queue.end(); ++it) {
            answer = multiply(answer, *it);
        }
        cout << answer.a[0][0] << ' ' << answer.a[0][1] << ' '
             << answer.a[1][0] << ' ' << answer.a[1][1] << '\n';
    }

    return 0;
}

一段指令的栈式摘要

删除操作总是删除最晚插入的矩阵，因此把每次插入看成压入“插入栈”，删除就是弹出栈顶。对一个固定分块从空栈开始扫描：

删除时若块内栈不空，就抵消块内最后一次插入；
否则记为一个未匹配删除，表示它将来会删除块外传入的栈顶；
扫描结束后，栈中剩余的插入按时间顺序组成存活插入序列。

所以分块可以摘要为 pop_count 和一段存活插入序列。把分块作用到已有栈时，先弹出 pop_count 个元素，再把存活插入序列整体压入。

分块栈与矩阵聚合

设一段插入序列中，所有头插入矩阵按最终顺序的乘积为 front，所有尾插入矩阵按最终顺序的乘积为 back。先后相接的两段序列 $A,B$ 满足：

front(A+B)=front(B)\times front(A),\qquad back(A+B)=back(A)\times back(B)。

每个分块预处理存活插入序列每个前缀的 (front, back)。查询时，区间两端不足一个分块的部分逐条执行，中间完整分块作为整体压入分块栈；删除操作如果只截断当前分块，就用对应前缀聚合量重算累计值。最终答案就是 front × back。

动态修改与查询

单点修改只影响所在分块，重新扫描该分块即可。一个区间至多包含两个边界分块和 $O(n/B)$ 个完整分块，其中 $B=320$ ，因此查询和修改复杂度均为 $O(B+n/B)$ 。

代码

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
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240/**
 * 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-07-31 16:21
 * update_at: 2026-08-17 22:40
 */
#include <bits/stdc++.h>
using namespace std;

const long long MOD = 998244353;
const int BLOCK_SIZE = 320;

// 2x2 矩阵
struct Matrix {
    long long a[2][2];
};

// 一条指令：type 1 头插，2 尾插，3 删除最晚插入的矩阵
struct Operation {
    int type;
    Matrix matrix;
};

// 一段插入序列聚合：front 为所有头插入按最终顺序的乘积，back 为所有尾插入的乘积
struct Aggregate {
    Matrix front;
    Matrix back;
};

// 一个分块的摘要：未匹配的删除个数 + 存活插入序列每个前缀的聚合
struct BlockSummary {
    int pop_count;
    vector<Aggregate> prefix;
};

// 分块栈中的一个元素：source 为分块编号（>=0）或单条指令（-index-1），length 为存活插入个数
struct ChunkState {
    int source;
    int length;
    Aggregate all; // 从栈底到当前元素的累计聚合
};

int n, event_count, block_count;
vector<Operation> operation;
vector<BlockSummary> block;
vector<ChunkState> chunk_stack;

Matrix identity_matrix() {
    Matrix result = {{{1, 0}, {0, 1}}};
    return result;
}

// 矩阵乘法，模 MOD
Matrix multiply(const Matrix &left, const Matrix &right) {
    Matrix result;
    result.a[0][0] = (left.a[0][0] * right.a[0][0]
        + left.a[0][1] * right.a[1][0]) % MOD;
    result.a[0][1] = (left.a[0][0] * right.a[0][1]
        + left.a[0][1] * right.a[1][1]) % MOD;
    result.a[1][0] = (left.a[1][0] * right.a[0][0]
        + left.a[1][1] * right.a[1][0]) % MOD;
    result.a[1][1] = (left.a[1][0] * right.a[0][1]
        + left.a[1][1] * right.a[1][1]) % MOD;
    return result;
}

Aggregate identity_aggregate() {
    Matrix identity = identity_matrix();
    return {identity, identity};
}

// 拼接两段插入序列：先出现 left 再出现 right。
// 头插入的最终顺序与出现顺序相反，尾插入的顺序相同。
Aggregate concatenate(const Aggregate &left, const Aggregate &right) {
    return {multiply(right.front, left.front), multiply(left.back, right.back)};
}

// 单条插入指令自身作为一个聚合
Aggregate operation_aggregate(int index) {
    Aggregate result = identity_aggregate();
    if (operation[index].type == 1) result.front = operation[index].matrix;
    if (operation[index].type == 2) result.back = operation[index].matrix;
    return result;
}

// 取一段长度为 length 的插入序列的聚合。
// source >= 0 表示分块编号，否则表示单条指令 -source-1。
Aggregate chunk_aggregate(int source, int length) {
    if (source >= 0) return block[source].prefix[length];
    if (length == 0) return identity_aggregate();
    return operation_aggregate(-source - 1);
}

// 重新扫描一个分块，生成其摘要：先抵消块内的删除，再对存活插入做前缀聚合
void rebuild_block(int id) {
    int left = id * BLOCK_SIZE;
    int right = min(n, left + BLOCK_SIZE);
    vector<int> push_operation; // 尚未被块内删除抵消的插入指令
    block[id].pop_count = 0;
    for (int i = left; i < right; i++) {
        if (operation[i].type == 3) {
            if (push_operation.empty()) block[id].pop_count++; // 未匹配删除
            else push_operation.pop_back();                    // 抵消最近一次插入
        } else {
            push_operation.push_back(i);
        }
    }

    // 对存活插入序列做前缀聚合
    block[id].prefix.clear();
    block[id].prefix.resize(push_operation.size() + 1, identity_aggregate());
    for (int i = 0; i < (int)push_operation.size(); i++) {
        block[id].prefix[i + 1] = block[id].prefix[i];
        int index = push_operation[i];
        if (operation[index].type == 1) {
            block[id].prefix[i + 1].front = multiply(
                operation[index].matrix, block[id].prefix[i].front);
        } else {
            block[id].prefix[i + 1].back = multiply(
                block[id].prefix[i].back, operation[index].matrix);
        }
    }
}

// 从分块栈顶弹出 count 个插入元素（模拟连续删除）
void pop_elements(int count) {
    while (count > 0 && !chunk_stack.empty()) {
        ChunkState &last = chunk_stack.back();
        if (last.length <= count) {
            count -= last.length;
            chunk_stack.pop_back();
        } else {
            // 只截断栈顶分块：用截断后的前缀聚合重算累计值
            last.length -= count;
            Aggregate before = chunk_stack.size() == 1
                ? identity_aggregate() : chunk_stack[chunk_stack.size() - 2].all;
            last.all = concatenate(before, chunk_aggregate(last.source, last.length));
            count = 0;
        }
    }
}

// 把一个完整分块压入栈，length 为它存活插入序列的长度
void append_chunk(int source, int length) {
    if (length == 0) return;
    Aggregate before = chunk_stack.empty() ? identity_aggregate() : chunk_stack.back().all;
    Aggregate current = chunk_aggregate(source, length);
    chunk_stack.push_back({source, length, concatenate(before, current)});
}

// 把单条指令作用到分块栈上
void apply_operation(int index) {
    if (operation[index].type == 3) {
        pop_elements(1);
    } else {
        Aggregate before = chunk_stack.empty() ? identity_aggregate() : chunk_stack.back().all;
        Aggregate current = before;
        if (operation[index].type == 1) {
            current.front = multiply(operation[index].matrix, before.front);
        } else {
            current.back = multiply(before.back, operation[index].matrix);
        }
        chunk_stack.push_back({-index - 1, 1, current});
    }
}

// 把整个分块作为摘要作用到栈上：先处理未匹配删除，再压入存活插入序列
void apply_block(int id) {
    pop_elements(block[id].pop_count);
    append_chunk(id, (int)block[id].prefix.size() - 1);
}

// 对区间 [left, right] 执行所有指令，返回最终队列矩阵乘积
Matrix query(int left, int right) {
    chunk_stack.clear();
    int index = left;
    while (index <= right) {
        int id = index / BLOCK_SIZE;
        int end = min(right, (id + 1) * BLOCK_SIZE - 1);
        // 完整块用摘要整体处理，边界块逐条执行
        if (index == id * BLOCK_SIZE && end - index + 1 == BLOCK_SIZE) {
            apply_block(id);
        } else {
            for (int i = index; i <= end; i++) apply_operation(i);
        }
        index = end + 1;
    }
    if (chunk_stack.empty()) return identity_matrix();
    return multiply(chunk_stack.back().all.front, chunk_stack.back().all.back);
}

// 读入一条指令
Operation read_operation() {
    Operation result;
    cin >> result.type;
    if (result.type == 1 || result.type == 2) {
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) cin >> result.matrix.a[i][j];
        }
    }
    return result;
}

void print_matrix(const Matrix &matrix) {
    cout << matrix.a[0][0] << ' ' << matrix.a[0][1] << ' '
         << matrix.a[1][0] << ' ' << matrix.a[1][1] << '\n';
}

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

    cin >> n >> event_count;
    operation.resize(n);
    for (int i = 0; i < n; i++) operation[i] = read_operation();

    // 预处理每个分块的摘要
    block_count = (n + BLOCK_SIZE - 1) / BLOCK_SIZE;
    block.resize(block_count);
    for (int i = 0; i < block_count; i++) rebuild_block(i);

    while (event_count--) {
        int type;
        cin >> type;
        if (type == 1) {
            // 单点修改：更新指令并重建所在分块
            int index;
            cin >> index;
            operation[index - 1] = read_operation();
            rebuild_block((index - 1) / BLOCK_SIZE);
        } else {
            int left, right;
            cin >> left >> right;
            print_matrix(query(left - 1, right - 1));
        }
    }

    return 0;
}

复杂度

设分块长 $B=320$ 。预处理所有分块为 $O(n)$ ；单点修改为 $O(B)$ ，一次区间查询为 $O(B+n/B)$ ；空间复杂度为 $O(n)$ 。矩阵乘法只涉及固定的 $2\times2$ 矩阵，单次乘法是常数时间。

总结

删除“最晚插入”使指令具有栈结构，根号分块可以把每块压缩成有限的未匹配删除和存活插入序列。分别维护头插入和尾插入的矩阵乘积，就能在动态修改下快速回答区间密码。

题目来自第 32 次 CSP 认证 T4，评测使用自造高质量复刻数据。我们承认原始题面与大样例版权均归中国计算机学会（CCF）所有，因此题面与评测服务均免费对外开放。如果您认为我们侵犯了您的权益，可联系我们。

时间限制： 1.5 秒

空间限制： 512 MB

题目描述

西西艾弗岛上埋藏着一份宝藏，小 C 根据藏宝图找到了宝藏的位置。藏有宝藏的箱子被上了锁，旁边写着一些提示：

给定 $n$ 条指令，编号为 $1 \sim n$ ，其中每条指令都是对一个双端队列的操作，队列中的元素均为 $2 \times 2$ 的矩阵；
在某些时刻，某一条指令可能会改变；
在某些时刻，密码可以由以下方式计算：对于给定的指令区间 $[l, r]$ ，对初始为空的队列依次执行第 $l \sim r$ 条指令，将得到的队列里的所有矩阵从头到尾相乘，并将乘积矩阵中的所有元素对 $998244353$ 取模，得到的矩阵即为密码；特别地，若队列为空，则密码为单位矩阵；如果能分别计算出这些时刻的密码，将能够打开箱子的锁，从而获得宝藏。

经过小 C 的观察，每条指令的形式均为以下三种之一：

给定 $2 \times 2$ 的矩阵 $\mathbf{A}$ ，将 $\mathbf{A}$ 插入队列的头部；
给定 $2 \times 2$ 的矩阵 $\mathbf{B}$ ，将 $\mathbf{B}$ 插入队列的尾部；
若队列非空，删除队列中最晚被插入的矩阵。

小 C 将所有的时刻发生的事件均记录了下来。具体地，共有 $m$ 个时刻，每个时刻可能会发生两种事件：

第 $i$ 条指令改变，改变后的指令仍为以上三种形式之一；
给定指令区间 $[l, r]$ ，求依次执行第 $l \sim r$ 条指令得到的密码。

由于小 C 并不会这个问题，他向你发起了求助。你需要帮助小 C 求出所有类型为 $2$ 的事件所对应的密码。

输入格式

从标准输入读入数据。

输入的第一行包含两个正整数 $n, m$ 。

接下来 $n$ 行，按顺序给出初始时刻的每条指令：

输入的第一个正整数 $v$ 描述这条指令的形式，保证 $v$ 为 $1, 2, 3$ 中的一种。
若 $v = 1$ ，接下来给出四个非负整数 $A_{1, 1}, A_{1, 2}, A_{2, 1}, A_{2, 2}$ ，表示操作为将 $2 \times 2$ 的矩阵 $\mathbf{A}$ 插入队列的头部；
若 $v = 2$ ，接下来给出四个非负整数 $B_{1, 1}, B_{1, 2}, B_{2, 1}, B_{2, 2}$ ，表示操作为将 $2 \times 2$ 的矩阵 $\mathbf{B}$ 插入队列的尾部；
若 $v = 3$ ，表示操作为若队列非空，删除队列中最晚被插入的矩阵；

接下来 $m$ 行，按顺序给出每个时刻发生的事件：

输入的第一个正整数 $v$ 描述这个事件的类型，保证 $v$ 为 $1, 2$ 中的一种。
若 $v = 1$ ，接下来给出一个正整数 $i$ 与一条指令，表示将第 $i$ 条指令更新为当前输入的指令，指令的输入格式与初始时刻指令的输入格式相同。
若 $v = 2$ ，接下来给出两个正整数 $l, r$ ，你需要求出依次执行第 $l \sim r$ 条指令得到的密码。

输出格式

输出到标准输出。

对于所有类型为 $2$ 的事件，输出一行四个非负整数 $C_{1, 1}, C_{1, 2}, C_{2, 1}, C_{2, 2}$ ，表示该时刻的密码 $\mathbf{C}$ 。

input1

1
2
3
4
5
6
7
83 4
1 2 3 9 3
2 6 9 4 2
2 2 8 2 1
2 2 3
1 2 1 3 1 0 1
1 3 3
2 1 3

output1

1
230 57 12 34
2 3 9 3

样例 1 解释

第一次事件发生时，

第 $2$ 条指令为在序列尾部插入矩阵 $\begin{bmatrix} 6 & 9 \\ 4 & 2 \end{bmatrix}$ ；
第 $3$ 条指令为在序列尾部插入矩阵 $\begin{bmatrix} 2 & 8 \\ 2 & 1 \end{bmatrix}$ 。

依次执行第 $2 \sim 3$ 条指令，得到的队列为 ${\begin{bmatrix} 6 & 9 \\ 4 & 2 \end{bmatrix}, \begin{bmatrix} 2 & 8 \\ 2 & 1 \end{bmatrix}}$ ，则密码为

\begin{bmatrix} 6 & 9 \\ 4 & 2 \end{bmatrix} \times \begin{bmatrix} 2 & 8 \\ 2 & 1 \end{bmatrix} = \begin{bmatrix} 30 & 57 \\ 12 & 34 \end{bmatrix}

第四次事件发生时，

第 $1$ 条指令为在序列头部插入矩阵 $\begin{bmatrix} 2 & 3 \\ 9 & 3 \end{bmatrix}$ ；
第 $2$ 条指令为在序列头部插入矩阵 $\begin{bmatrix} 3 & 1 \\ 0 & 1 \end{bmatrix}$ ；
第 $3$ 条指令为若队列非空，删除队列中最晚被插入的矩阵。

依次执行第 $1 \sim 3$ 条指令，得到的队列为 ${\begin{bmatrix} 2 & 3 \\ 9 & 3 \end{bmatrix}}$ ，则密码为 $\begin{bmatrix} 2 & 3 \\ 9 & 3 \end{bmatrix}$ 。

样例 2

见题目文件区的 2.in 与 2.ans。

样例 2 解释

该样例满足子任务 1 的限制。

样例 3

见题目文件区的 3.in 与 3.ans。

样例 3 解释

该样例满足子任务 2 的限制。

样例 4

见题目文件区的 4.in 与 4.ans。

样例 4 解释

该样例满足子任务 4 的限制。

样例 5

见题目文件区的 5.in 与 5.ans。

样例 5 解释

该样例满足子任务 4 的限制。

样例 6

见题目文件区的 6.in 与 6.ans。

样例 6 解释

该样例满足子任务 5 的限制。

样例 7

见题目文件区的 7.in 与 7.ans。

样例 7 解释

该样例满足子任务 6 的限制。

子任务

对于所有测试数据，满足 $1 \leq n, m \leq 10 ^ 5$ ， $0 \leq A_{i, j}, B_{i, j} < 998244353$ ， $1 \leq l \leq r \leq n$ 。

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。

子任务编号	分值	$n,m\le$	特殊性质
1	15	$10^2$	无
2	20	$10^3$	无
3	10	$5\times 10^4$	所有指令的形式均为 $1$
4	10	$5\times 10^4$	所有指令的形式均为 $1$ 或 $2$
5	20	$5\times 10^4$	所有事件的类型均为 $2$
6	10	$5\times 10^4$	无
7	15	$10^5$	无

宝藏

目录

形式化题目

思路

一段指令的栈式摘要

分块栈与矩阵聚合

动态修改与查询

代码

复杂度

总结