题解 P6242 【模板】线段树 3
warzone
·
·
题解
相信不少初学者对于 区间取 max/min 接受尚可，而对于 区间历史最值 一脸懵逼。
如果我们不满足于认识现有的结果，就要发掘出问题背后的脉络，
认识到看起来“神机妙算”的证明，拆掉之前的脚手架长什么样。
Carl Friedrich Gauss: “凡是有自尊心的建筑师，在瑰丽的大厦建成之后，决不会把脚手架留在那里。”
（摘自 EI's blog）
本文将指出，看似神机妙算的区间历史最值，其实是个简单的线性代数问题。
首先我们要明晰线段树为什么能够实现区间信息的快速维护。
对于 【模板】线段树 1：
给定序列 a，m 次操作：
-
- 求 \displaystyle\sum_{i=l}^r a_i 。
通过线段树上每个点存储 所辖区间的 a_i 之和，即可实现快速查询。
想一想为什么这么做是对的，易发现原因是 加法满足结合律：
a_l+a_{l+1}+\cdots+a_{mid}+a_{mid+1}+a_{mid+2}+\cdots+a_r
=(a_l+a_{l+1}+\cdots+a_{mid})+(a_{mid+1}+a_{mid+2}+\cdots+a_r)
接下来，通过在线段树上打 懒标记 ，即可实现快速修改。
同样的，其原因是 加法满足结合律和交换律：
(a_i+k)+l=a_i+(k+l)
(a_l+k)+(a_{l+1}+k)+\cdots+(a_r+k)=(a_l+a_{l+1}+\cdots+a_r)+(r-l+1)k
在此基础上，对于【模板】线段树 2，分别维护加法和乘法标记，
采取 先乘后加 的推标记方法，即可实现快速修改。
其原因是 乘法满足结合律，且对加法满足分配律：
(a_i\times k)\times l=a_i\times(k\times l)
a_l\times k+a_{l+1}\times k+\cdots+a_r\times k=(a_l+a_{l+1}+\cdots+a_r)\times k
接下来，我们看看最基础的区间历史最值问题。
给定序列 a,b，初始 a=b，m 次操作：
-
- 求 \displaystyle\max_{i=l}^ra_i 。
- 求 \displaystyle\max_{i=l}^rb_i 。
每次操作后，我们都进行一次更新，让 b_i\leftarrow \max(b_i,a_i)。
这里，我们只要维护 +,\max 两种运算，它们满足
- 交换律：a+b=b+a,\max(a,b)=\max(b,a) 。
- 结合律：(a+b)+c=a+(b+c),\max(\max(a,b),c)=\max(a,\max(b,c)) 。
- 单位元：a+0=0+a=a,\max(a,-\infty)=\max(-\infty,a)=a 。
- 加法逆元（相反数）：a+(-a)=(-a)+a=0 。
- 分配律：a+\max(b,c)=\max(a+b,a+c),\max(a,b)+c=\max(a+c,b+c) 。
这时，我们发现，如果将 \max 作为矩阵元素的加法，
> 维护向量序列 $\displaystyle\left\{{a_i\brack b_i}\right\},m$ 次操作：
> - $\forall i\in[l,r],\displaystyle{a_i\brack b_i}_{_{}}\leftarrow\begin{bmatrix}k&-\infty\\ -\infty&0\end{bmatrix}{a_i\brack b_i}$ 。
> - 求 $\displaystyle {a_l\brack b_l}+{a_{l+1}\brack b_{l+1}}+\cdots+{a_r\brack b_r}$，$+$ 为向量加法。
>
> 每次操作后，令 $\displaystyle{a_i\brack b_i}\leftarrow\begin{bmatrix}0&-\infty\\ 0&0\end{bmatrix}{a_i\brack b_i}$ 。
根据矩阵的运算律，相信大家已经发现了维护的方法：
维护 向量之和 与 矩阵乘法标记 即可。
但 矩阵乘法标记 还可以再简化，因为
$$\begin{bmatrix}a&-\infty\\b&0\end{bmatrix}+\begin{bmatrix}c&-\infty\\d&0\end{bmatrix}=\begin{bmatrix}\max(a,c)&-\infty\\\max(b,d)&0\end{bmatrix}$$
$$\begin{bmatrix}a&-\infty\\b&0\end{bmatrix}\begin{bmatrix}c&-\infty\\d&0\end{bmatrix}=\begin{bmatrix}a+c&-\infty\\\max(b+c,d)&0\end{bmatrix}$$
于是对于 $\begin{bmatrix}c&-\infty\\d&0\end{bmatrix}$ 只要维护 $\displaystyle{c\brack d}$ 即可。
事实上，$c,d$ 即对应论文中的 “加减标记” 和 “历史最大加减标记”。
----------------------------
回到本题，本题在上面的基础上还支持区间取 $\min$ 和区间求和，即
> - $\forall i\in[l,r],a_i\leftarrow \min(a_i,k)$ 。
> - 求 $\displaystyle\sum_{i=l}^r a_i$ 。
回想下不维护区间历史最值时是怎样维护区间取 min 的。实际上，我们是通过摊还分析，
划分最大值与次大值，将区间取 min 转化为 **对最大值的区间加减** 来维护的。
对于本题，沿用这一思路。
我们将 $\displaystyle{a_i\brack b_i}$ 按照 $a_i$ 的大小划分 。具体地，每个节点维护如下信息：
- $\overrightarrow{mx}$：$a_i$ 最大的 $\displaystyle{a_i\brack b_i}_{}$ 之和。
- $\overrightarrow{se}$：$a_i$ 非最大的 $\displaystyle{a_i\brack b_i}$ 之和。
- 矩阵 $M$：对 $\overrightarrow{mx}$ 的矩阵乘法标记。
- 矩阵 $E$：对 $\overrightarrow{se}$ 的矩阵乘法标记。
线段树维护即可。
特别地，尽管区间求和不能用矩阵来表示，
但也是可以集成到这棵线段树上的，这里留给读者作为思考题。
---------------------------
令我吃惊的是，在此之前并没有一篇题解是基于矩阵来理解吉老师线段树的，
显然矩阵让各个操作的组织变得容易了许多。
希望这篇题解能让初学者不被繁杂的标记劝退，少走弯路，更深入地理解这个数据结构。
```cpp
/*
this code is made by warzone
2022.2.14 21:25
*/
#include<stdio.h>
#include<string.h>
typedef long long ll;
typedef unsigned int word;
struct READ{//快读
char pool[5<<22],*top,w;
inline READ(){fread(top=pool,5<<22,1,stdin);}
template<typename type>
inline READ& operator >>(type& num){
for(w=1;'0'>*top||*top>'9';)
w=*(top++)=='-'? -1:1;
for(num=0;'0'<=*top&&*top<='9';)
num=num*10+(*(top++)-'0');
return num*=w,*this;
}
}cin;
const int inf=0x80000000;//−∞
inline int max(const int a,const int b){
return a>b? a:b;}
/* 向量/矩阵
⎡a⎤ ⎡a −∞⎤
⎣b⎦ ⎣b 0⎦
*/
struct matrix{
int a,b;
inline matrix(){}
inline matrix(const matrix &p)=default;
inline matrix(int A,int B):a(A),b(B){}
inline matrix operator+(const matrix &p)const{//矩阵/向量 加法
return matrix(max(a,p.a),max(b,p.b));}
inline matrix operator()(const matrix &p)const{//矩阵乘法
return matrix(a==inf||p.a==inf? inf:a+p.a,
b==inf||p.a==inf? p.b:max(b+p.a,p.b));}
inline bool operator!=(const matrix &p)const{
return a!=p.a||b!=p.b;}
}const I(0,inf),vec0(inf,inf);
word n,m;
struct segment_tree{//线段树（zkw）
ll sum[1u<<20];
int cnt[1u<<20];
matrix mx[1u<<20],M[1u<<20];
matrix se[1u<<20],E[1u<<20];
inline segment_tree(){
for(word i=0;i<(1u<<20);++i) M[i]=E[i]=I;
se[1u<<19]=vec0,cnt[1u<<19]=1,cin>>n>>m;
for(int i=(1u<<19)+1,num;i<=(1u<<19|n);++i){
se[i]=vec0,cnt[i]=1,cin>>num;
sum[i]=mx[i].a=mx[i].b=num;
}
for(word i=(1u<<19|n)+1;i<(1u<<20);++i)
se[i]=vec0,cnt[i]=1;
for(word i=(1u<<19)-1;i;--i) pushup(i);
}
#define l (rt<<1)
#define r (rt<<1|1)
inline void pushup(const word rt){//上传信息
sum[rt]=sum[l]+sum[r];
if(mx[l].a>mx[r].a){
mx[rt]=mx[l],cnt[rt]=cnt[l];
se[rt]=se[l]+se[r]+mx[r];
}else if(mx[l].a<mx[r].a){
mx[rt]=mx[r],cnt[rt]=cnt[r];
se[rt]=se[l]+se[r]+mx[l];
}else{
mx[rt]=mx[l]+mx[r];
cnt[rt]=cnt[l]+cnt[r];
se[rt]=se[l]+se[r];
}
}
inline void Mmul(const matrix &p,const word id){//修改 mx
mx[id]=p(mx[id]),M[id]=p(M[id]),sum[id]+=1ll*cnt[id]*p.a;}
inline void Emul(const matrix &p,const word id,const word size){//修改 se
se[id]=p(se[id]),E[id]=p(E[id]);
sum[id]+=1ll*(size-cnt[id])*p.a;
}
inline void pushdown(const word rt,const word size){//下传标记
Mmul(mx[l].a==mx[rt].a-M[rt].a? M[rt]:E[rt],l);
Mmul(mx[r].a==mx[rt].a-M[rt].a? M[rt]:E[rt],r);
//注意此处不能用 mx[l].a 和 mx[r].a 的大小关系来判断划分，因为标记下传后 mx 会被修改
if(size!=1) Emul(E[rt],l,size),Emul(E[rt],r,size);
M[rt]=E[rt]=I;
}
inline void plus(const word f,const word t,const int k,
const word rt=1,const word size=1u<<18){//区间加
if(size==0||(f==0&&t==(size<<1)-1))
return Mmul(matrix(k,k),rt),Emul(matrix(k,k),rt,size? size<<1:1);
auto lf=[&](word f,word t){plus(f,t,k,l,size>>1);};
auto rf=[&](word f,word t){plus(f,t,k,r,size>>1);};
pushdown(rt,size);
if(f&size) rf(f&~size,t&~size);
else if((t&size)^size) lf(f,t);
else lf(f,size-1),rf(0,t&~size);
pushup(rt);
}
inline void min(const word f,const word t,const int k,
const word rt=1,const word size=1u<<18){//区间取 min
if(k>=mx[rt].a) return;
const auto lf=[&](word f,word t){min(f,t,k,l,size>>1);};
const auto rf=[&](word f,word t){min(f,t,k,r,size>>1);};
if(size==0||(f==0&&t==(size<<1)-1)){
if(k>se[rt].a) return Mmul(matrix(k-mx[rt].a,k-mx[rt].a),rt);
return pushdown(rt,size),lf(0,size-1),rf(0,size-1),pushup(rt);
}
pushdown(rt,size);
if(f&size) rf(f&~size,t&~size);
else if((t&size)^size) lf(f,t);
else lf(f,size-1),rf(0,t&~size);
pushup(rt);
}
inline ll getsum(const word f,const word t,
const word rt=1,const word size=1u<<18){//区间求和
if(size==0||(f==0&&t==(size<<1)-1)) return sum[rt];
const auto lf=[&](word f,word t)->ll{return getsum(f,t,l,size>>1);};
const auto rf=[&](word f,word t)->ll{return getsum(f,t,r,size>>1);};
pushdown(rt,size);
if(f&size) return rf(f&~size,t&~size);
else if((t&size)^size) return lf(f,t);
return lf(f,size-1)+rf(0,t&~size);
}
inline int geta(const word f,const word t,
const word rt=1,const word size=1u<<18){//区间最值
if(size==0||(f==0&&t==(size<<1)-1)) return mx[rt].a;
const auto lf=[&](word f,word t)->ll{return geta(f,t,l,size>>1);};
const auto rf=[&](word f,word t)->ll{return geta(f,t,r,size>>1);};
pushdown(rt,size);
if(f&size) return rf(f&~size,t&~size);
else if((t&size)^size) return lf(f,t);
return max(lf(f,size-1),rf(0,t&~size));
}
inline int getb(const word f,const word t,
const word rt=1,const word size=1u<<18){//区间历史最值
if(size==0||(f==0&&t==(size<<1)-1)) return max(mx[rt].b,se[rt].b);
const auto lf=[&](word f,word t)->ll{return getb(f,t,l,size>>1);};
const auto rf=[&](word f,word t)->ll{return getb(f,t,r,size>>1);};
pushdown(rt,size);
if(f&size) return rf(f&~size,t&~size);
else if((t&size)^size) return lf(f,t);
return max(lf(f,size-1),rf(0,t&~size));
}
#undef l
#undef r
}tree;
int main(){
for(int opt,l,r;m;--m)
if(cin>>opt>>l>>r,opt==1)
cin>>opt,tree.plus(l,r,opt);
else if(opt==2) cin>>opt,tree.min(l,r,opt);
else if(opt==4) printf("%d\n",tree.geta(l,r));
else if(opt==5) printf("%d\n",tree.getb(l,r));
else printf("%lld\n",tree.getsum(l,r));
return 0;
}
```