警示后人：注意乘法顺序
查看原帖
警示后人：注意乘法顺序
555833
haozexu楼主2024/1/27 11:01

如果您是像这样设计的转移矩阵：

[fx,0fx,1]∗[∞gx,1gx,0gx,1]=[fy,0fy,1]\begin{bmatrix} f_{x,0}&f_{x,1} \end{bmatrix}*\begin{bmatrix} \infty & g_{x,1}\\ g_{x,0}& g_{x,1} \end{bmatrix} = \begin{bmatrix} f_{y,0}&f_{y,1} \end{bmatrix}

请注意f矩阵其实也是很多g矩阵连乘出来的。

矩阵乘法不满足交换律，为了满足从下往上更新的策略，线段树中必须是右子树（dfn大）乘左子树（dfn小），才是正确的转移顺序

2024/1/27 11:01