CCF-CSP认证考试 202312-4 宝藏 100分题解
时间：2024-04-10 21:40:32 来源：网络cs 作者：峨乐 栏目：国内电商 阅读：
更多 CSP 认证考试题目题解可以前往：CCF-CSP 认证考试真题题解
原题链接： 202312-4 宝藏
时间限制： 1.5s
内存限制： 512.0MB
问题描述
西西艾弗岛上埋藏着一份宝藏，小 C 根据藏宝图找到了宝藏的位置。藏有宝藏的箱子被上了锁，旁边写着一些提示：
给定 n n n 条指令，编号为 1 ∼ n 1 \sim n 1∼n，其中每条指令都是对一个双端队列的操作，队列中的元素均为 2 × 2 2 \times 2 2×2 的矩阵；在某些时刻，某一条指令可能会改变；在某些时刻，密码可以由以下方式计算：对于给定的指令区间 [ l , r ] [l, r] [l,r]，对初始为空的队列依次执行第 l ∼ r l \sim r l∼r 条指令，将得到的队列里的所有矩阵从头到尾相乘，并将乘积矩阵中的所有元素对 998244353 998244353 998244353 取模，得到的矩阵即为密码；特别地，若队列为空，则密码为单位矩阵；如果能分别计算出这些时刻的密码，将能够打开箱子的锁，从而获得宝藏。经过小 C 的观察，每条指令的形式均为以下三种之一：
给定 2 × 2 2 \times 2 2×2 的矩阵 A \mathbf{A} A，将 A \mathbf{A} A 插入队列的头部；给定 2 × 2 2 \times 2 2×2 的矩阵 B \mathbf{B} B，将 B \mathbf{B} B 插入队列的尾部；若队列非空，删除队列中最晚被插入的矩阵。小 C 将所有的时刻发生的事件均记录了下来。具体地，共有 m m m 个时刻，每个时刻可能会发生两种事件：
第 i i i 条指令改变，改变后的指令仍为以上三种形式之一；给定指令区间 [ l , r ] [l, r] [l,r]，求依次执行第 l ∼ r l \sim r l∼r 条指令得到的密码。由于小 C 并不会这个问题，他向你发起了求助。你需要帮助小 C 求出所有类型为 2 2 2 的事件所对应的密码。
输入格式
从标准输入读入数据。
输入的第一行包含两个正整数 n , m n, m n,m。
接下来 n n n 行，按顺序给出初始时刻的每条指令：
输入的第一个正整数 v v v 描述这条指令的形式，保证 v v v 为 1 , 2 , 3 1, 2, 3 1,2,3 中的一种。若 v = 1 v = 1 v=1，接下来给出四个非负整数 A 1 , 1 , A 1 , 2 , A 2 , 1 , A 2 , 2 A_{1, 1}, A_{1, 2}, A_{2, 1}, A_{2, 2} A1,1,A1,2,A2,1,A2,2，表示操作为将 2 × 2 2 \times 2 2×2 的矩阵 A \mathbf{A} A 插入队列的头部；若 v = 2 v = 2 v=2，接下来给出四个非负整数 B 1 , 1 , B 1 , 2 , B 2 , 1 , B 2 , 2 B_{1, 1}, B_{1, 2}, B_{2, 1}, B_{2, 2} B1,1,B1,2,B2,1,B2,2，表示操作为将 2 × 2 2 \times 2 2×2 的矩阵 B \mathbf{B} B 插入队列的尾部；若 v = 3 v = 3 v=3，表示操作为若队列非空，删除队列中最晚被插入的矩阵；接下来 m m m 行，按顺序给出每个时刻发生的事件：
输入的第一个正整数 v v v 描述这个事件的类型，保证 v v v 为 1 , 2 1, 2 1,2 中的一种。若 v = 1 v = 1 v=1，接下来给出一个正整数 i i i 与一条指令，表示将第 i i i 条指令更新为当前输入的指令，指令的输入格式与初始时刻指令的输入格式相同。若 v = 2 v = 2 v=2，接下来给出两个正整数 l , r l, r l,r，你需要求出依次执行第 l ∼ r l \sim r l∼r 条指令得到的密码。输出格式
输出到标准输出。
对于所有类型为 2 2 2 的事件，输出一行四个非负整数 C 1 , 1 , C 1 , 2 , C 2 , 1 , C 2 , 2 C_{1, 1}, C_{1, 2}, C_{2, 1}, C_{2, 2} C1,1,C1,2,C2,1,C2,2，表示该时刻的密码 C \mathbf{C} C。
样例1输入
3 41 2 3 9 32 6 9 4 22 2 8 2 12 2 31 2 1 3 1 0 11 3 32 1 3样例1输出
30 57 12 342 3 9 3样例解释
第一次事件发生时，
第 2 2 2 条指令为在序列尾部插入矩阵 [ 6 9 4 2 ] \begin{bmatrix} 6 & 9 \\ 4 & 2 \end{bmatrix} [6492]；第 3 3 3 条指令为在序列尾部插入矩阵 [ 2 8 2 1 ] \begin{bmatrix} 2 & 8 \\ 2 & 1 \end{bmatrix} [2281]。依次执行第 2 ∼ 3 2 \sim 3 2∼3 条指令，得到的队列为 { [ 6 9 4 2 ] , [ 2 8 2 1 ] } \left\{\begin{bmatrix} 6 & 9 \\ 4 & 2 \end{bmatrix}, \begin{bmatrix} 2 & 8 \\ 2 & 1 \end{bmatrix}\right\} {[6492],[2281]}，则密码为
[ 6 9 4 2 ] × [ 2 8 2 1 ] = [ 30 57 12 34 ] \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} [6492]×[2281]=[30125734]
第四次事件发生时，
第 1 1 1 条指令为在序列头部插入矩阵 [ 2 3 9 3 ] \begin{bmatrix} 2 & 3 \\ 9 & 3 \end{bmatrix} [2933]；第 2 2 2 条指令为在序列头部插入矩阵 [ 3 1 0 1 ] \begin{bmatrix} 3 & 1 \\ 0 & 1 \end{bmatrix} [3011]；第 3 3 3 条指令为若队列非空，删除队列中最晚被插入的矩阵。依次执行第 1 ∼ 3 1 \sim 3 1∼3 条指令，得到的队列为 { [ 2 3 9 3 ] } \left\{\begin{bmatrix} 2 & 3 \\ 9 & 3 \end{bmatrix}\right\} {[2933]}，则密码为 [ 2 3 9 3 ] \begin{bmatrix} 2 & 3 \\ 9 & 3 \end{bmatrix} [2933]。
子任务
对于所有测试数据，满足 1 ≤ n , m ≤ 1 0 5 1 \le n, m \le 10 ^ 5 1≤n,m≤105， 0 ≤ A i , j , B i , j < 998244353 0 \le A_{i, j}, B_{i, j} < 998244353 0≤Ai,j,Bi,j<998244353， 1 ≤ l ≤ r ≤ n 1 \le l \le r \le n 1≤l≤r≤n。
| 测试点编号 | n , m ≤ n, m \le n,m≤ | 特殊性质 |
|---|---|---|
| 1 ∼ 3 1 \sim 3 1∼3 | 1 0 2 10 ^ 2 102 | 无 |
| 4 ∼ 7 4 \sim 7 4∼7 | 1 0 3 10 ^ 3 103 | 无 |
| 8 , 9 8, 9 8,9 | 5 × 1 0 4 5 \times 10 ^ 4 5×104 | 所有指令的形式均为 1 1 1 |
| 10 , 11 10, 11 10,11 | 5 × 1 0 4 5 \times 10 ^ 4 5×104 | 所有指令的形式均为 1 1 1 或 2 2 2 |
| 12 ∼ 15 12 \sim 15 12∼15 | 5 × 1 0 4 5 \times 10 ^ 4 5×104 | 所有事件的类型均为 2 2 2 |
| 16 , 17 16, 17 16,17 | 5 × 1 0 4 5 \times 10 ^ 4 5×104 | 无 |
| 18 ∼ 20 18 \sim 20 18∼20 | 1 0 5 10 ^ 5 105 | 无 |
题解
先考虑指令的化简，指令 1 , 2 1,2 1,2 可以进行合并，例如指令 1 1 1，在队列的头部插入 A \mathbf{A} A 的同时，在队列的尾部同时插入单位阵 B = ( 1 0 0 1 ) \mathbf{B}=\begin{pmatrix}1&0\\0&1\end{pmatrix} B=(1001)；指令 2 2 2 同理。如此合并后，指令 3 3 3 变为同时从最列的头部和尾部各删除一个矩阵。
其次考虑指令 3 3 3 的匹配问题，这其实就是一个括号匹配问题，将指令 1 , 2 1,2 1,2 看成 (，指令 3 3 3 看成 )，将匹配的括号利用栈删除，余下的形式一定为 )...)(...( 的形式（若干个指令 3 3 3 在前面，后面是若干个指令 1 , 2 1,2 1,2），最终仅需计算剩余的 ( 所对应的矩阵的乘积。例如最后栈中剩余的指令的序号为 { i 1 , i 2 , ⋯ , i k } \{i_1,i_2,\cdots,i_k\} {i1,i2,⋯,ik}，那么，所求的密码即为 A i k ⋯ A i 2 A i 1 B i 1 B i 2 ⋯ B i k \mathbf{A}_{i_k}\cdots\mathbf{A}_{i_2}\mathbf{A}_{i_1}\mathbf{B}_{i_1}\mathbf{B}_{i_2}\cdots\mathbf{B}_{i_k} Aik⋯Ai2Ai1Bi1Bi2⋯Bik。
使用分块算法，将原先给的 n n n 个操作分成 n \sqrt n n 个块，对于每个块记录一下信息：
neg：未匹配的指令 3 3 3 的条数，即上文中 ) 的个数。sz：栈中剩余的指令个数，即上文中 ( 的个数，也是上文中的 k k k。suml、sumr：剩余的指令的矩阵的前缀积，例如 s u m l [ 2 ] = A i 2 A i 1 \mathtt{suml[2]}=\mathbf{A}_{i_2}\mathbf{A}_{i_1} suml[2]=Ai2Ai1， s u m r [ 3 ] = B i 1 B i 2 B i 3 \mathtt{sumr[3]}=\mathbf{B}_{i_1}\mathbf{B}_{i_2}\mathbf{B}_{i_3} sumr[3]=Bi1Bi2Bi3，注意矩阵乘法的顺序问题。 开始读入完 n n n 条指令后，先对每个块进行初始化，处理出上述变量的值。然后开始处理 m m m 条事件：
对于更新事件，用新指令替换原先指令，然后像初始化过程类似的重新计算那个块的相关信息。由于块长是 n \sqrt n n ，单次更新的时间复杂度是 O ( n ) \mathcal{O}(\sqrt n) O(n )。对于查询事件 如果 l ∼ r l\sim r l∼r 之间的长度足够小（ l , r l,r l,r 在同一个块中），直接暴力地去模拟出剩余的序列，依次乘起来就行。该类查询的复杂度不会超过 O ( n ) \mathcal{O}(\sqrt n) O(n )。将整个 l ∼ r l\sim r l∼r 分成 3 3 3 段， l , r l,r l,r 所属的块各一段，剩余的所有总共一段。从后往前依次合并。 最后的一段（ r r r 所属的块）直接暴力模拟即可，同时需要记录) 的个数 NEG，用于去和前面块的 ( 进行匹配从而删除，总共不超过 n \sqrt n n 个指令。中间的一段是由若干个完整的块组成（该段也有可能不存在，直接跳过即可），从后往前处理所有的块，判断 NEG 和当前块的 sz 的大小，如果 sz <= NEG 的话，该块中的所有指令均会被移除，同时要将当前块的 neg 加到 NEG 中，即 NEG = NEG - sz + neg；如果 sz > NEG，则指令最终会剩余 sz - NEG 个，利用之前处理好的 suml、sumr 即可 O ( 1 ) \mathcal{O}(1) O(1) 计算出当前块对答案的贡献，将记录答案的矩阵乘上对应的矩阵即可，如此操作后新的 NEG = neg。由于最多存在 n \sqrt n n 个块，则该部分的复杂度不超过 O ( n ) \mathcal{O}(\sqrt n) O(n )。第一段（ l l l 所属的块） 直接暴力模拟即可，总共不超过 n \sqrt n n 个指令。该类查询的复杂度不会超过 O ( 3 n ) \mathcal{O}(3\sqrt n) O(3n )。 时间复杂度： O ( n + m n ) \mathcal{O}(n+m\sqrt n) O(n+mn )。
在更新的时候也可以采用懒更新的方式，在更新某条指令的时候，只是把那条指令替换掉，不去计算块的相关变量，而是给那个块打个标记，代表该块中有内容发生修改，在查询到有标记的块时再去更新那个块中的相关信息。该方法会有一定的加速，但是时间复杂度不变。
此外，该题也可以使用线段树的方法来写，时间复杂度为 O ( ( n + m ) log 2 n ) \mathcal{O}((n+m)\log^2n) O((n+m)log2n)。
参考代码（750ms，10.78MB）
/* Created by Pujx on 2024/2/2.*/#pragma GCC optimize(2, 3, "Ofast", "inline")#include <bits/stdc++.h>using namespace std;#define endl '\n'//#define int long long//#define double long doubleusing i64 = long long;using ui64 = unsigned long long;using i128 = __int128;#define inf (int)0x3f3f3f3f3f3f3f3f#define INF 0x3f3f3f3f3f3f3f3f#define yn(x) cout << (x ? "yes" : "no") << endl#define Yn(x) cout << (x ? "Yes" : "No") << endl#define YN(x) cout << (x ? "YES" : "NO") << endl#define mem(x, i) memset(x, i, sizeof(x))#define cinarr(a, n) for (int i = 1; i <= n; i++) cin >> a[i]#define cinstl(a) for (auto& x : a) cin >> x;#define coutarr(a, n) for (int i = 1; i <= n; i++) cout << a[i] << " \n"[i == n]#define coutstl(a) for (const auto& x : a) cout << x << ' '; cout << endl#define all(x) (x).begin(), (x).end()#define md(x) (((x) % mod + mod) % mod)#define ls (s << 1)#define rs (s << 1 | 1)#define ft first#define se second#define pii pair<int, int>#ifdef DEBUG #include "debug.h"#else #define dbg(...) void(0)#endifconst int N = 1e5 + 5;const int M = 350 + 5;const int mod = 998244353;//const int mod = 1e9 + 7;//template <typename T> T ksm(T a, i64 b) { T ans = 1; for (; b; a = 1ll * a * a, b >>= 1) if (b & 1) ans = 1ll * ans * a; return ans; }//template <typename T> T ksm(T a, i64 b, T m = mod) { T ans = 1; for (; b; a = 1ll * a * a % m, b >>= 1) if (b & 1) ans = 1ll * ans * a % m; return ans; }//int a[N];int n, m, t, k, q;struct mat { int v[2][2]; mat(bool isE = false) { v[0][0] = v[1][1] = isE; v[1][0] = v[0][1] = 0; } friend mat operator * (const mat& a, const mat& b) { mat ans; ans.v[0][0] = (1ll * a.v[0][0] * b.v[0][0] + 1ll * a.v[0][1] * b.v[1][0]) % mod; ans.v[0][1] = (1ll * a.v[0][0] * b.v[0][1] + 1ll * a.v[0][1] * b.v[1][1]) % mod; ans.v[1][0] = (1ll * a.v[1][0] * b.v[0][0] + 1ll * a.v[1][1] * b.v[1][0]) % mod; ans.v[1][1] = (1ll * a.v[1][0] * b.v[0][1] + 1ll * a.v[1][1] * b.v[1][1]) % mod; return ans; } friend istream& operator >> (istream& in, mat& x) { return in >> x.v[0][0] >> x.v[0][1] >> x.v[1][0] >> x.v[1][1]; } friend ostream& operator << (ostream& out, const mat& x) { for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) out << x.v[i][j] << " "; return out; }};struct node { int op; mat l, r; friend istream& operator >> (istream& in, node& nd) { in >> nd.op; if (nd.op == 1) in >> nd.l, nd.r = mat(true); else if (nd.op == 2) in >> nd.r, nd.l = mat(true); else nd.l = nd.r = mat(true); return in; }} op[N];int len;struct block { int l, r, neg, sz; mat suml[M], sumr[M]; void build(int idx) { l = idx * len, r = min(l + len - 1, n - 1), neg = 0, sz = 0; deque<int> st; for (int i = l; i <= r; i++) { if (op[i].op != 3) st.push_back(i); else if (st.empty()) neg++; else st.pop_back(); } sz = st.size(); suml[0] = sumr[0] = mat(true); for (int i = 0; i < st.size(); i++) { suml[i + 1] = op[st[i]].l * suml[i]; sumr[i + 1] = sumr[i] * op[st[i]].r; } }} blk[M];mat query(int l, int r) { int blkl = l / len, blkr = r / len; if (blkl == blkr) { // 直接模拟 deque<int> st; for (int i = l; i <= r; i++) if (op[i].op != 3) st.push_back(i); else if (!st.empty()) st.pop_back(); mat L = mat(true), R = mat(true); for (int i = 0; i < st.size(); i++) { L = op[st[i]].l * L; R = R * op[st[i]].r; } return L * R; } else { int neg = 0; deque<int> st; for (int i = blk[blkr].l; i <= r; i++) { if (op[i].op != 3) st.push_back(i); else if (st.empty()) neg++; else st.pop_back(); } mat L = mat(true), R = mat(true); for (int i = 0; i < st.size(); i++) { L = op[st[i]].l * L; R = R * op[st[i]].r; } for (int i = blkr - 1; i >= blkl + 1; i--) { if (blk[i].sz <= neg) neg = neg - blk[i].sz + blk[i].neg; else { L = L * blk[i].suml[blk[i].sz - neg]; R = blk[i].sumr[blk[i].sz - neg] * R; neg = blk[i].neg; } } while (!st.empty()) st.pop_back(); for (int i = l; i <= blk[blkl].r; i++) { if (op[i].op != 3) st.push_back(i); else if (!st.empty()) st.pop_back(); } while (neg && !st.empty()) neg--, st.pop_back(); for (int i = st.size() - 1; i >= 0; i--) { L = L * op[st[i]].l; R = op[st[i]].r * R; } return L * R; }}void work() { cin >> n >> m; len = max(1, (int)sqrt(n)); for (int i = 0; i < n; i++) cin >> op[i]; for (int i = 0; i < n; i += len) blk[i / len].build(i / len); while (m--) { int v, idx, l, r; cin >> v; if (v == 1) { cin >> idx; cin >> op[--idx]; blk[idx / len].build(idx / len); } else { cin >> l >> r; cout << query(--l, --r) << endl; } }}signed main() {#ifdef LOCAL freopen("C:\\Users\\admin\\CLionProjects\\Practice\\data.in", "r", stdin); freopen("C:\\Users\\admin\\CLionProjects\\Practice\\data.out", "w", stdout);#endif ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int Case = 1; //cin >> Case; while (Case--) work(); return 0;}/* _____ _ _ _ __ __ | _ \ | | | | | | \ \ / / | |_| | | | | | | | \ \/ / | ___/ | | | | _ | | } { | | | |_| | | |_| | / /\ \ |_| \_____/ \_____/ /_/ \_\*/阅读本书更多章节>>>>关于代码的亿点点说明：
代码的主体部分位于void work()函数中，另外会有部分变量申明、结构体定义、函数定义在上方。#pragma ...是用来开启 O2、O3 等优化加快代码速度。中间一大堆#define ...是我习惯上的一些宏定义，用来加快代码编写的速度。"debug.h"头文件是我用于调试输出的代码，没有这个头文件也可以正常运行（前提是没定义DEBUG宏），在程序中如果看到dbg(...)是我中途调试的输出的语句，可能没删干净，但是没有提交上去没有任何影响。ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);这三句话是用于解除流同步，加快输入cin输出cout速度（这个输入输出流的速度很慢）。在小数据量无所谓，但是在比较大的读入时建议加这句话，避免读入输出超时。如果记不下来可以换用scanf和printf，但使用了这句话后，cin和scanf、cout和printf不能混用。将main函数和work函数分开写纯属个人习惯，主要是为了多组数据。
本文链接：https://www.kjpai.cn/guonei/2024-04-10/156774.html，文章来源：网络cs，作者：峨乐，版权归作者所有，如需转载请注明来源和作者，否则将追究法律责任！