区间历史操作，从矩阵乘法到标记

· · 题解

Part1 前言

可能我是不喜爱繁杂推导的人，看了多篇题解都没能理解线段树历史最值的标记，于是手写了一个矩阵乘法的版本，就感觉都能理解了，所以这篇文章送给有一定矩阵（线性代数）基础又不能理解线段树历史最值的人。

Part2 矩阵乘法的性质

两个矩阵 A_{n,m},B_{m,p} 相乘得到 C_{n,p}，满足 C_{n,p}=\sum A_{n,i}B_{i,p}。

而处理区间最值和历史最值时，常用广义矩乘，即 C_{n,p}=\max (A_{n,i}+B_{i,p})。

矩阵乘法和广义矩阵乘法均具有结合律。

Part3 区间历史最值维护

考虑序列每一个数维护一个向量 \begin{bmatrix}a_i\\b_i\end{bmatrix}，a_i 表示当前值，b_i 表示历史最值，用线段树维护区间向量和（即 a_i,b_i 的最大值）。

那么区间加 k 可以看作 \begin{bmatrix}a\\b\end{bmatrix}\leftarrow\begin{bmatrix}a+k\\\max\{b,a+k\}\end{bmatrix}，可以很容易地构造广义矩阵乘法：\begin{bmatrix}a\\b\end{bmatrix}\begin{bmatrix}k&k\\-\infty&0\end{bmatrix}=\begin{bmatrix}a+k\\\max\{b,a+k\}\end{bmatrix}，故可以将懒标记设为 \begin{bmatrix}k&k\\-\infty&0\end{bmatrix} 这个矩阵。

不过本题需要支持区间赋值，这个操作可以转化为区间加，就是即使线段树节点被区间完包，只要最大值不等于最小值，就递归下去，根据颜色段均摊理论，这部分的均摊时间复杂度为 O(n)。

当然也可以给向量再加一维，使其变为 \begin{bmatrix}a\\b\\0\end{bmatrix}，这样就有 \begin{bmatrix}a\\b\\0\end{bmatrix}\begin{bmatrix}-\infty&-\infty&-\infty\\-\infty&0&-\infty\\k&k&0\end{bmatrix}=\begin{bmatrix}k\\\max\{b,k\}\\0\end{bmatrix}。

其实看到这里你已经能 AC 本题了，因为我也是这样写的。

Part4 将矩阵转为标记

事实上本题没有区间最值操作，只是让你稍微理解一下历史最值的实现方式，公认的例题还是 线段树 3。

这道题由于拥有区间最值操作，所以要对最大值和非最大值分别打标记，当然你会发现这道题的所有标记均为加上一个值，所以可以用矩阵 \begin{bmatrix}k&k\\-\infty&0\end{bmatrix} 来表示标记。

当然最初我只会使用分块来维护，本地就要跑 7s，稳稳地超时，由此可见，矩阵乘法的 k^3 很多时候并不能当常数看待。

考虑两个标记结合（相乘），会得到什么：\begin{bmatrix}k_1&k_2\\-\infty&0\end{bmatrix}\begin{bmatrix}k_3&k_4\\-\infty&0\end{bmatrix}=\begin{bmatrix}k_1+k_3&\max\{k_2,k_1+k_4\}\\-\infty&0\end{bmatrix}，从实际意义来考虑，A_{1,1} 表示当前加值，A_{1,2} 表示历史最大加值。

所以我们只需要对最大值和非最大值分别记录 tag1 表示当前加值，tag2 表示历史最大加值，经过一系列卡常，甚至将块长调到了 120，终于通过了此题。

至此，线段树和分块就没什么两样了，除了常数较小。

Part5 普通矩阵乘法与区间历史和

大致模型如 NOIP2022 比赛，事实上研究矩乘本来就是为了学习这道题的做法，据说都被出烂了。

题意求 \sum\limits_{L\le l\le r\le R}\max\limits_{i=l}^ra_i\max\limits_{i=l}^rb_i，需要用扫描线转换为历史和。

其实就是从 1 到 n 扫右端点，用线段树维护序列 A_i=\max\limits_{j=i}^ra_j,B_i=\max\limits_{j=i}^rb_j 的乘积历史和。

容易发现 A_i,B_i 是单调的，而每一次会全局与 a_r,b_r 取 \max，直接做是不好维护的，可以用单调栈或直接暴力颜色段均摊转化为区间加，考虑每一个节点维护向量：\begin{bmatrix}a\\b\\ab\\c\\len\end{bmatrix}，表示区间 A_i,B_i 的和，A_iB_i 的和，A_iB_i 的历史和，区间长度。考虑如何区间加。

我们需要 \begin{bmatrix}a\\b\\ab\\c\\len\end{bmatrix}\leftarrow\begin{bmatrix}a+k\times len\\b\\ab+k\times b\\c\\len\end{bmatrix}，可以构造矩阵乘法：

\begin{bmatrix}a\\b\\ab\\c\\len\end{bmatrix}\begin{bmatrix}1&0&0&0&0\\0&1&k&0&0\\0&0&1&0&0\\0&0&0&1&0\\k&0&0&0&1\end{bmatrix}=\begin{bmatrix}a+k\times len\\b\\ab+k\times b\\c\\len\end{bmatrix}

同理，有区间 B_i 增加 k：

\begin{bmatrix}a\\b\\ab\\c\\len\end{bmatrix}\begin{bmatrix}1&0&k&0&0\\0&1&0&0&0\\0&0&1&0&0\\0&0&0&1&0\\0&k&0&0&1\end{bmatrix}=\begin{bmatrix}a\\b+k\times len\\ab+k\times a\\c\\len\end{bmatrix}

当然，操作结束时需要对区间 1\sim r 更新历史和：

\begin{bmatrix}a\\b\\ab\\c\\len\end{bmatrix}\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}=\begin{bmatrix}a\\b\\ab\\c+ab\\len\end{bmatrix}

至此，你已经可以在 k^3(n+q)\log n（其中 k=5） 的时间复杂度内解决此题了，在场上能获得 76 分，还不够优秀。

要知道，矩阵乘法更多是用来理解标记的，而不是用在代码实现上的。

发现矩阵的主对角线永远都为 1，有一些项永远都为 0，为什么呢？因为矩阵的每一个元素 A_{i,j} 都可以视作 i 对 j 产生的贡献，而这个贡献会形成一个有向无环图（偏序集）：len\rightarrow a,b\rightarrow ab\rightarrow c，可以看出，每一个矩阵最多只有 9 个有效状态，这样我们就大大减小了常数，可以轻松通过。

Part6 后记

这些众所周知的东西能多学就多学一点吧。