「THUSCH 2017」大魔法师

# 「THUSCH 2017」大魔法师 —— 题解 ----- ### 传送门：[LOJ 2980](https://loj.ac/problem/2980) ---- #### 思路：**矩阵乘法**， 可以把每一个操作看成乘上一个矩阵，或者加上一个矩阵 如下： ---------- 对于$1$操作，可以这么处理： $$\begin{bmatrix} 1&1&0 \\ 0&1&0\\0&0&1\end{bmatrix}\times \begin{bmatrix} A\\B\\C\end{bmatrix}=\begin{bmatrix} A+B\\B\\C\end{bmatrix}$$ $2,3$操作同理。 --------- 对于$4$操作，可以这么处理： $$\begin{bmatrix} v\\0\\0\end{bmatrix}+\begin{bmatrix} A\\B\\C\end{bmatrix}=\begin{bmatrix} A+v\\B\\C\end{bmatrix}$$ -------- 对于$5$操作，可以这么处理： $$\begin{bmatrix} 1&0&0\\0&v&0\\0&0&1\end{bmatrix}\times\begin{bmatrix} A\\B\\C\end{bmatrix}=\begin{bmatrix} A\\B*v\\C\end{bmatrix}$$ -------- 对于$6$操作，可以这么处理： $$\begin{bmatrix} 1&0&0\\0&1&0\\0&0&0\end{bmatrix}\times\begin{bmatrix} A\\B\\C\end{bmatrix}=\begin{bmatrix} A\\B\\0\end{bmatrix}$$ $$\begin{bmatrix} 0\\0\\v\end{bmatrix}+\begin{bmatrix} A\\B\\0\end{bmatrix}=\begin{bmatrix} A\\B\\v\end{bmatrix}$$ 即： $$\begin{bmatrix} 0\\0\\v\end{bmatrix}+\begin{bmatrix} 1&0&0\\0&1&0\\0&0&0\end{bmatrix}\times\begin{bmatrix} A\\B\\C\end{bmatrix}=\begin{bmatrix} A\\B\\v\end{bmatrix}$$ -------------- 到这里，所有的操作对应的转移矩阵都已经有了， 还有最后一个问题就是： 运算顺序该怎么办？ 线段树$down$操作的时候，是先加还是先乘？ 貌似都错的。 --------- 转换一下思路： 给你一个数列， 支持$3$种操作： 1.区间加值 2.区间乘值 3.区间求和 思路：维护一个$lazy\_time(k)$和$lazy\_add(b)$ 乘值得时候把$lazy\_add$也乘上该值即可， $down$的时候先乘后加 --------- 那么矩阵的运算有什么性质来着？ 能不能转换成一个形如“矩阵$B+$矩阵$K\times$初始矩阵$X$”的形式呢？ #### 加值的情况 在加值的时候，可以直接加到矩阵$B$上， ### 乘值得情况 在乘值得时候，$B$和$K$同时乘上即可， （因为矩阵乘法满足分配率） 但是要注意乘$K$的时候，是$K$在后面。 （矩阵乘法不满足交换律） 知道这些之后就能写了。 ---------