线段树
一般线段树维护的东西是什么？设其维护的信息的半群 \((A,+)\)，维护标记的半群 \((T,\times)\) 和一种运算 \(*\mapsto A*T\to A\)。
要求 \((b+c)*a=b*a+c*a\)。
一般而言，矩阵是满足这东西的最一般东西，所以线段树一定可以用矩阵搞。
注意：这里不包括 Segment Tree Beats 等基于势能分析的非传统线段树。
现在我们看题：[NOIP2022] 比赛。
扫描线，然后单调栈转化成支持 \(a·b\) 历史和、\(a,b\) 区间覆盖的数据结构。
想在 \(O(1)\) 秒钟构造出标记感觉不大现实，考虑用矩阵乘法维护标记，记 \(a,b,S,len\) 为区间 \(a/b\) 和，历史版本和，区间长度，则区间 \(a\) 加上 \(v\) 就是
\[\begin{bmatrix}a+vlen&b&ab+bv&S&len\end{bmatrix}=\begin{bmatrix}a&b&ab&S&len\end{bmatrix}\times \begin{bmatrix} 1&0&0&0&0\\0&1&v&0&0\\0&0&1&0&0\\0&0&0&1&0\\v&0&0&0&1\\\end{bmatrix}
\]
区间 \(b\) 加就是：
\[\begin{bmatrix}a&b+vlen&ab+av&S&len\end{bmatrix}=\begin{bmatrix}a&b&ab&S&len\end{bmatrix}\times \begin{bmatrix} 1&0&v&0&0\\0&1&0&0&0\\0&0&1&0&0\\0&0&0&1&0\\0&v&0&0&1\\\end{bmatrix}
\]
叠加上版本和就是：
\[\begin{bmatrix}a&b&ab&S+ab&len\end{bmatrix}=\begin{bmatrix}a&b&ab&S&len\end{bmatrix}\times \begin{bmatrix} 1&0&0&0&0\\0&1&0&0&0\\0&0&1&1&0\\0&0&0&1&0\\0&0&0&0&1\\\end{bmatrix}
\]
然后线段树维护矩阵即可，时间复杂度 \(O((n+m)k^3\log n),k=5\)，由于常数过大，可以获得 \(20pts\) 的高分。
然后我们发现，矩阵有很多地方用不上，可以直接拆开。
贡献是形如 \(len\to a,b\to ab\to S\) 的 DAG，最多有 \(9\) 个状态，然后我们只维护这 \(9\) 个数即可。
然后发现这些位置分别是 \((4,0),(4,1),(4,2),(4,3),(0,2),(0,3),(1,2),(1,3),(2,3)\)
然后把这一部分重新标号，拿出来手动维护就行了。
代码没写
联考题
代码待补