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

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

#include<cstdio>
const int MAXN = 1e5 + 5;
const int inf = 0x7fffffff;

inline int max(int a,int b){ return a>b? a: b;}
inline void chk_max(int &a,int b){ if(a<b) a=b;}

int ans[MAXN<<2],max_ans[MAXN<<2];//区间最大值	区间历史最大值 

bool vis[MAXN<<2];//是否进行过区间赋值操作 
int sum[MAXN<<2], val[MAXN<<2];//上次下放之后的加和	上次下放之后的赋值操作 （赋值之后的加操作一并算入赋值，下同）
int max_sum[MAXN<<2], max_val[MAXN<<2];//上次下放之后达到的最大加和	上次下放之后赋的最大值 
/*
注意这里实际上使用了4个lazy_tag，不过如果您理解了算法的核心，您应该知道我在干什么
*/
#define ls(u) ((u)<<1)
#define rs(u) ((u)<<1|1)//个人习惯，左右儿子


inline void push_up(int u)//push_up比较简单，就是用左右儿子的答案更新本节点的答案
{
    ans[u] = max(ans[ls(u)], ans[rs(u)]);
    max_ans[u] = max(max_ans[ls(u)], max_ans[rs(u)]);
}


//我将更新lazy_tag的操作打包成函数，不然有可能在细节上出错（其实我一开始就是在这里出的错）
/*
更新加操作的tag，分为两种情况：
 1.赋过值，算作赋值操作
 2.没赋过值
*/
inline void do_sum(int u,int k,int max_k)//max_k表示父节点在上一次push_down之后达到的最大加和
{
    if(vis[u])
    {
        chk_max(max_val[u], val[u]+max_k);
        chk_max(max_ans[u], ans[u]+max_k);
        ans[u]+=k;
        val[u]+=k;
    }
    else
    {
        chk_max(max_sum[u], sum[u]+max_k);
        chk_max(max_ans[u], ans[u]+max_k);
        ans[u]+=k;
        sum[u]+=k;
    }
}

inline void do_val(int u,int k,int max_k)//max_k表示父节点在上一次push_down之后达到的最大赋值
{
	if(vis[u])
	{
		chk_max(max_val[u], max_k);
    	chk_max(max_ans[u], max_k);
	}
    else
    {
    	vis[u]=1;//该点标记为赋过值
    	max_val[u] = max_k;
    	chk_max(max_ans[u], max_k);
	}
    ans[u] = val[u] = k;
}

inline void push_down(int u)
{
    do_sum(ls(u),sum[u],max_sum[u]);
    do_sum(rs(u),sum[u],max_sum[u]);//先传递和
    
    sum[u] = max_sum[u] = 0;//下传之后清零
    
    if(vis[u])
    {
        do_val(ls(u),val[u],max_val[u]);
        do_val(rs(u),val[u],max_val[u]);
        
        vis[u] = 0;
        val[u] = max_val[u] = 0;//下传之后清零
    }
}

void build(int u,int l,int r)//建树
{
    if(l==r)
    {
        scanf("%d",&ans[u]);
        max_ans[u]=ans[u];
        return;
    }
    
    int mid=(l+r)>>1;
    build(ls(u),l,mid);
    build(rs(u),mid+1,r);
    push_up(u);
}

int query(int u,int l,int r, int ql,int qr)//Q操作
{
    if(ql<=l && r<=qr) return ans[u];
    
    push_down(u);
    int mid=(l+r)>>1, ret=-inf;
    if(ql<=mid) ret = query(ls(u),l,mid, ql,qr);
    if(mid<qr) chk_max(ret, query(rs(u),mid+1,r, ql,qr));
    
    return ret;
}

int query_max(int u,int l,int r, int ql,int qr)//A操作，与Q类似
{
    if(ql<=l && r<=qr) return max_ans[u];
    
    push_down(u);
    int mid=(l+r)>>1, ret=-inf;
    if(ql<=mid) ret = query_max(ls(u),l,mid, ql,qr);
    if(mid<qr) chk_max(ret, query_max(rs(u),mid+1,r, ql,qr));
    
    return ret;
}

void add(int u,int l,int r, int ql,int qr,int k)//P操作
{
    if(ql<=l && r<=qr)
    {
        do_sum(u,k,k);//这里max_k也填k就行了
        return;
    }
    
    push_down(u);
    int mid = (l+r)>>1;
    if(ql<=mid) add(ls(u),l,mid, ql,qr,k);
    if(mid<qr) add(rs(u),mid+1,r, ql,qr,k);
    push_up(u);
}

void assign(int u,int l,int r, int ql,int qr,int k)//C操作
{
    if(ql<=l && r<=qr)
    {
        do_val(u,k,k);
        return;
    }
    
    push_down(u);
    int mid = (l+r)>>1;
    if(ql<=mid) assign(ls(u),l,mid, ql,qr,k);
    if(mid<qr) assign(rs(u),mid+1,r, ql,qr,k);
    push_up(u);
}

//这两个函数是调试用的，用于打印序列
void print(int u,int l,int r)
{
    if(l==r)
    {
        printf("%d ",ans[u]);
        return;
    }
    push_down(u);
    int mid=(l+r)>>1;
    print(ls(u),l,mid);
    print(rs(u),mid+1,r);
}
inline void test(int t)
{
    printf("=========================================\n");
    print(1,1,t);
    printf("\n=========================================\n");
}

int main(void)
{
    int t;
    scanf("%d",&t);
    build(1,1,t);
    
    int e;
    scanf("%d",&e);
    while(e--)
    {
        char c=getchar();
        while(c!='Q' && c!='A' && c!='P' && c!='C') c=getchar();//个人习惯，感觉这么写比较保险 
        int x,y;
        scanf("%d%d",&x,&y);
        
        if(c=='Q') printf("%d\n",query(1,1,t, x,y));
        if(c=='A') printf("%d\n",query_max(1,1,t, x,y));
        if(c=='P')
        {
            int z;
            scanf("%d",&z);
            add(1,1,t, x,y,z);
            //test(t);
        }
        if(c=='C')
        {
            int z;
            scanf("%d",&z);
            assign(1,1,t, x,y,z);
            //test(t);
        }
    }
    return 0;
}