P16067 [CSPro 32] Treasure

The testdata on Luogu are only for non-official community use and are not official testdata. Official judging link: .

On Xixi-Aifu Island, a treasure is buried. Little C found the treasure’s location according to a treasure map. The treasure chest is locked, and there are some hints written beside it: - You are given $n$ instructions, numbered $1 \sim n$. Each instruction is an operation on a **deque**, and all elements in the deque are $2 \times 2$ matrices. - At certain times, some instruction may be modified. - At certain times, the password can be computed as follows: for a given instruction interval $[l, r]$, starting from an empty deque, execute instructions $l \sim r$ in order. Multiply all matrices in the resulting deque from front to back, and take every entry of the product matrix modulo $998244353$. The resulting matrix is the password. In particular, if the deque is empty, the password is the **identity matrix**. If you can compute the passwords at these times, you will be able to open the chest and obtain the treasure. After observing, Little C found that each instruction is always one of the following three forms: 1. Given a $2 \times 2$ matrix $\mathbf{A}$, insert $\mathbf{A}$ at the front of the deque. 2. Given a $2 \times 2$ matrix $\mathbf{B}$, insert $\mathbf{B}$ at the back of the deque. 3. If the deque is not empty, delete the matrix that was inserted **most recently**. Little C recorded all events that happened over time. Specifically, there are $m$ time points, and at each time point one of the following two types of events may occur: 1. Instruction $i$ changes; the modified instruction is still one of the three forms above. 2. Given an instruction interval $[l, r]$, compute the password obtained by executing instructions $l \sim r$ in order. Since Little C does not know how to solve this problem, he asks you for help. You need to output the password for every event of type 2.

Read input from standard input. The first line contains two positive integers $n, m$. The next $n$ lines give the instructions at the initial time in order: - The first integer $v$ describes the form of the instruction, and $v$ is guaranteed to be one of $1, 2, 3$. - If $v = 1$, then four non-negative integers $A_{1,1}, A_{1,2}, A_{2,1}, A_{2,2}$ follow, meaning the operation is to insert the $2 \times 2$ matrix $\mathbf{A}$ at the front of the deque. - If $v = 2$, then four non-negative integers $B_{1,1}, B_{1,2}, B_{2,1}, B_{2,2}$ follow, meaning the operation is to insert the $2 \times 2$ matrix $\mathbf{B}$ at the back of the deque. - If $v = 3$, it means: if the deque is not empty, delete the matrix that was inserted **most recently**. The next $m$ lines describe the events at each time point in order: - The first integer $v$ describes the type of the event, and $v$ is guaranteed to be one of $1, 2$. - If $v = 1$, then a positive integer $i$ and an instruction follow, meaning to update instruction $i$ to the given instruction. The input format of the instruction is the same as in the initial instructions. - If $v = 2$, then two positive integers $l, r$ follow; you need to compute the password obtained by executing instructions $l \sim r$ in order.

Write output to standard output. For every event of type $2$, output one line with four non-negative integers $C_{1,1}, C_{1,2}, C_{2,1}, C_{2,2}$, representing the password matrix $\mathbf{C}$ at that time.

### Explanation for Sample 1 When the first event happens: - Instruction $2$ inserts the matrix $\begin{bmatrix} 6 & 9 \\ 4 & 2 \end{bmatrix}$ at the back of the sequence. - Instruction $3$ inserts the matrix $\begin{bmatrix} 2 & 8 \\ 2 & 1 \end{bmatrix}$ at the back of the sequence. Executing instructions $2 \sim 3$ in order, the resulting deque is $\begin{bmatrix} 6 & 9 \\ 4 & 2 \end{bmatrix}, \begin{bmatrix} 2 & 8 \\ 2 & 1 \end{bmatrix}$, so the password is $$ \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} $$ When the fourth event happens: - Instruction $1$ inserts the matrix $\begin{bmatrix} 2 & 3 \\ 9 & 3 \end{bmatrix}$ at the front of the sequence. - Instruction $2$ inserts the matrix $\begin{bmatrix} 3 & 1 \\ 0 & 1 \end{bmatrix}$ at the front of the sequence. - Instruction $3$ means: if the deque is not empty, delete the matrix that was inserted most recently. Executing instructions $1 \sim 3$ in order, the resulting deque is $\begin{bmatrix} 2 & 3 \\ 9 & 3 \end{bmatrix}$, so the password is $\begin{bmatrix} 2 & 3 \\ 9 & 3 \end{bmatrix}$. ### Sample 2 See `2.in` and `2.ans` under the problem directory. This sample satisfies the constraints of testdata $1 \sim 3$. ### Sample 3 See `3.in` and `3.ans` under the problem directory. This sample satisfies the constraints of testdata $4 \sim 7$. ### Sample 4 See `4.in` and `4.ans` under the problem directory. This sample satisfies the constraints of testdata $8, 9$. ### Sample 5 See `5.in` and `5.ans` under the problem directory. This sample satisfies the constraints of testdata $10, 11$. ### Sample 6 See `6.in` and `6.ans` under the problem directory. This sample satisfies the constraints of testdata $12 \sim 15$. ### Sample 7 See `7.in` and `7.ans` under the problem directory. This sample satisfies the constraints of testdata $16, 17$. ### Subtasks For all testdata, it holds that $1 \le n, m \le 10^5$, $0 \le A_{i,j}, B_{i,j} < 998244353$, and $1 \le l \le r \le n$. | Test Point ID | $n, m \le$ | Special Property | |:-------------:|:----------:|:----------------:| | $1 \sim 3$ | $10^2$ | None | | $4 \sim 7$ | $10^3$ | ^ | | $8, 9$ | $5 \times 10^4$ | All instructions are of form $1$ | | $10, 11$ | ^ | All instructions are of form $1$ or $2$ | | $12 \sim 15$ | ^ | All events are of type $2$ | | $16, 17$ | ^ | None | | $18 \sim 20$ | $10^5$ | ^ | Translated by ChatGPT 5