今天在做区间历史和。感觉给每个标记一个含义实在太抽象了，遂听从白神建议学习矩阵维护信息和优化半群结构。
前置知识：大魔法师，用矩阵维护轮换信息。我们发现区间历史和事实上是对“历史和”变量被“和”变量轮换加法的结果，不知道为什么以前没反应过来和大魔法师有关。
区间加和区间历史和
用这个来进行举例。
我们考虑我们做区间加和区间历史和需要的信息。不难想到应该有三个：\(sum\) 表示区间现在的和，\(l\) 表示区间的长度，\(hsum\) 表示区间历史和。把它写成矩阵（或者说列向量）形如：\(\begin{bmatrix}sum \\l \\ hsum\end{bmatrix}\)。
考虑区间加操作，使用一些构造能力构造懒标记即可，很容易得到：
\[\begin{bmatrix} 1 & v & 0\\ 0 & 1 & 0\\ 0 & 0 & 1 \end{bmatrix} \times \begin{bmatrix} sum \\ l \\ hsum \end{bmatrix} = \begin{bmatrix} sum+lv \\ l \\ hsum \end{bmatrix} \]这样就维护好了。注意我们把列向量的信息放到右边，这样每次新信息都可以利用旧信息的每一项转移。
那么也容易构造刷新历史和：
\[\begin{bmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ 1 & 0 & 1 \end{bmatrix} \times \begin{bmatrix} sum \\ l \\ hsum \end{bmatrix} = \begin{bmatrix} sum \\ l \\ hsum+sum \end{bmatrix} \]直接用大魔法师一样的办法用矩阵乘法合并懒标记就行。注意新来的标记往旧标记的前面乘才是正确顺序。
但是这样太慢了。
我们发现矩阵里面有很多位置是没用的。我们可以通过刻画标记合并的式子来观察哪些位置是会变化的，哪些位置会是定值。比如我们发现：
\[\begin{bmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ 1 & 0 & 1 \end{bmatrix} \times \begin{bmatrix} 1 & v & 0\\ 0 & 1 & 0\\ 0 & 0 & 1 \end{bmatrix} = \begin{bmatrix} 1 & v & 0\\ 0 & 1 & 0\\ 1 & v & 1 \end{bmatrix} \]我们发现只有三个位置 \(A_{01},A_{20},A_{21}\) 在三个矩阵中是不一样的。其他位置都一模一样。我们把这三个位置在两个矩阵里都用字母替掉可以发现乘出来的矩阵也只有这三个位置会有变化，那么无论怎么乘下去都是这三个位置。
换而言之，一个矩阵的确定只需要这三个元素就够了。所以我们考虑优化半群结构，我们只需要设计一个和矩阵等价的运算可以维护这三个值的变化即可。我们把这三个值放回转移里面发现：
\[\begin{bmatrix} 1 & a & 0\\ 0 & 1 & 0\\ b & c & 1 \end{bmatrix} \times \begin{bmatrix} 1 & a' & 0\\ 0 & 1 & 0\\ b' & c' & 1 \end{bmatrix} = \begin{bmatrix} 1 & a'+a & 0\\ 0 & 1 & 0\\ b'+b & a'b+c+c' & 1 \end{bmatrix} \]所以我们直接维护 \(\text{tag}=\{a,b,c\}\) 即可。注意新的运算仍然不存在交换律，打标记时需要左乘。
考虑写出矩阵和信息（那个列向量）的乘法来确定标记和信息乘在一起的形态。
标签：begin,end,线段,矩阵,hsum,bmatrix,半群,优化,sum From： https://www.cnblogs.com/lemonniforever/p/18387546