c++ CCF-CSP认证考试 202312-4 宝藏 100分题解

更多 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 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

样例1输出

30 57 12 34

2 3 9 3

样例解释

第一次事件发生时，

第

2

2

2 条指令为在序列尾部插入矩阵

[

6

9

4

2

]

\begin{bmatrix} 6 & 9 \\ 4 & 2 \end{bmatrix}

[64​92​]；第

3

3

3 条指令为在序列尾部插入矩阵

[

2

8

2

1

]

\begin{bmatrix} 2 & 8 \\ 2 & 1 \end{bmatrix}

[22​81​]。

依次执行第

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\}

{[64​92​],[22​81​]}，则密码为

[

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}

[64​92​]×[22​81​]=[3012​5734​]

第四次事件发生时，

第

1

1

1 条指令为在序列头部插入矩阵

[

2

3

9

3

]

\begin{bmatrix} 2 & 3 \\ 9 & 3 \end{bmatrix}

[29​33​]；第

2

2

2 条指令为在序列头部插入矩阵

[

3

1

0

1

]

\begin{bmatrix} 3 & 1 \\ 0 & 1 \end{bmatrix}

[30​11​]；第

3

3

3 条指令为若队列非空，删除队列中最晚被插入的矩阵。

依次执行第

1

∼

3

1 \sim 3

1∼3 条指令，得到的队列为

{

[

2

3

9

3

]

}

\left\{\begin{bmatrix} 2 & 3 \\ 9 & 3 \end{bmatrix}\right\}

{[29​33​]}，则密码为

[

2

3

9

3

]

\begin{bmatrix} 2 & 3 \\ 9 & 3 \end{bmatrix}

[29​33​]。

子任务

对于所有测试数据，满足

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=(10​01​)；指令

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​​⋯Ai2​​Ai1​​Bi1​​Bi2​​⋯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]=Ai2​​Ai1​​，

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]=Bi1​​Bi2​​Bi3​​，注意矩阵乘法的顺序问题。

开始读入完

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

using namespace std;

#define endl '\n'

//#define int long long

//#define double long double

using 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

#ifdef DEBUG

#include "debug.h"

#else

#define dbg(...) void(0)

#endif

const int N = 1e5 + 5;

const int M = 350 + 5;

const int mod = 998244353;

//const int mod = 1e9 + 7;

//template 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 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 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 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 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 函数分开写纯属个人习惯，主要是为了多组数据。

好文链接

 您阅读本篇文章共花了：