柒葉灬 的博客

柒葉灬 的博客

「THUSCH 2017」大魔法师

posted on 2019-04-06 18:33:22 | under 题解 |

「THUSCH 2017」大魔法师 —— 题解


传送门:LOJ 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$ 在后面。

(矩阵乘法不满足交换律)

知道这些之后就能写了。