自动搬运

查看原文

来自洛谷，原作者为

	EnofTaiPeople MGXS

搬运于2025-08-24 21:58:53，当前版本为作者最后更新于2023-02-18 12:49:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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 后记

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