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 的观察，每条指令的形式均为以下三种之一：

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

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

  1. 第 i i i 条指令改变，改变后的指令仍为以上三种形式之一；
  2. 给定指令区间 [ 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 > x.v[1][1]; } friend ostream& operator for (int i = 0; i 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 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 m; len = max(1, (int)sqrt(n)); for (int i = 0; i > op[i]; for (int i = 0; i > v; if (v == 1) { cin >> idx; cin >> op[--idx]; blk[idx / len].build(idx / len); } else { cin >> l >> r; cout #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; } /* _____ _ _ _ __ __ | _ \ | | | | | | \ \ / / | |_| | | | | | | | \ \/ / | ___/ | | | | _ | | } { | | | |_| | | |_| | / /\ \ |_| \_____/ \_____/ /_/ \_\ */

          关于代码的亿点点说明：

          1. 代码的主体部分位于 void work() 函数中，另外会有部分变量申明、结构体定义、函数定义在上方。
          2. #pragma ... 是用来开启 O2、O3 等优化加快代码速度。
          3. 中间一大堆 #define ... 是我习惯上的一些宏定义，用来加快代码编写的速度。
          4. "debug.h" 头文件是我用于调试输出的代码，没有这个头文件也可以正常运行（前提是没定义 DEBUG 宏），在程序中如果看到 dbg(...) 是我中途调试的输出的语句，可能没删干净，但是没有提交上去没有任何影响。
          5. ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); 这三句话是用于解除流同步，加快输入 cin 输出 cout 速度（这个输入输出流的速度很慢）。在小数据量无所谓，但是在比较大的读入时建议加这句话，避免读入输出超时。如果记不下来可以换用 scanf 和 printf，但使用了这句话后，cin 和 scanf、cout 和 printf 不能混用。
          6. 将 main 函数和 work 函数分开写纯属个人习惯，主要是为了多组数据。