区间加区间历史和，在网上的博客已经烂大街了。但还没有区间覆盖区间历史和。
众所周知，我们一般把线段树上维护的分类为信息与懒标记。用矩阵乘法的角度来看就是 I 和 T 两个矩阵。
线段树上，我们要处理信息与信息合并，信息与懒标记合并，懒标记与懒标记合并。
信息与信息合并就是矩阵相加。其他两个是乘。
于是定义 \(I=\begin{pmatrix}H\\V\\L\end{pmatrix}\)，H 表示历史和，V 表示当前区间和，L 表示区间长。
此时，发现区间覆盖 z 就是 \(T=\begin{pmatrix}1&0&0\\0&0&z\\0&0&1\end{pmatrix}\)，将当前的和加入历史和就是 \(T=\begin{pmatrix}1&1&0\\0&1&0\\0&0&1\end{pmatrix}\)
可以用一个传递闭包的技巧，发现懒标记与懒标记合并后，矩阵 T 总可写为 \(T=\begin{pmatrix}1&A&B\\0&C&D\\0&0&1\end{pmatrix}\)。
下传标记时，信息与懒标记合并：
\[\begin{pmatrix}
1&A&B\\
0&C&D\\
0&0&1
\end{pmatrix}\begin{pmatrix}H\\ V\\ L\end{pmatrix}=\begin{pmatrix}H+AV+BL\\ CV+DL\\ L\end{pmatrix}\]
懒标记与懒标记合并：
\[\begin{pmatrix}
1&A&B\\
0&C&D\\
0&0&1
\end{pmatrix}
\begin{pmatrix}
1&a&b\\
0&c&d\\
0&0&1
\end{pmatrix}
=
\begin{pmatrix}
1&a+Ac&b+B+Ad\\
0&Cc&Cd+D\\
0&0&1
\end{pmatrix}
\]
其中小写字母表示原标记，大写字母表示下传的标记。
P3246 [HNOI2016] 序列
扫描线转化后即为区间覆盖区间历史和。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<tuple>
using ll=long long;
using std::max;
using std::min;
template<class T> void cmax(T&a,T b){a=max(a,b);}
template<class T> void cmin(T&a,T b){a=min(a,b);}
/*
1 A B 1 a b 1 a+Ac b+B+Ad
C D c d Cc Cd+D
1 1 1
*/
namespace segt{
struct SEGN{
ll v,h,a,b,c,d;
} tr[400005];
void dotag(int x,int l,int r,ll A,ll B,ll C,ll D){
//std::tie(tr[x].h,tr[x].v)=std::tie(tr[x].h+A*tr[x].v+B*(r-l+1),tr[x].v*C+D*(r-l+1));
tr[x].h+=A*tr[x].v+B*(r-l+1);
tr[x].v=tr[x].v*C+D*(r-l+1);
//std::tie(tr[x].a,tr[x].b,tr[x].c,tr[x].d)=std::tie(
// tr[x].a+A*tr[x].c,tr[x].b+B+A*tr[x].d,tr[x].c*C,tr[x].d*C+D);
tr[x].a+=A*tr[x].c;
tr[x].b+=B+A*tr[x].d;
tr[x].c*=C;
tr[x].d=tr[x].d*C+D;
}void dn(int x,int l,int r){
int mid=l+r>>1;
if(tr[x].a||tr[x].b||tr[x].d||tr[x].c!=1){
dotag(x*2,l,mid,tr[x].a,tr[x].b,tr[x].c,tr[x].d);
dotag(x*2+1,mid+1,r,tr[x].a,tr[x].b,tr[x].c,tr[x].d);
tr[x].a=tr[x].b=tr[x].d=0;
tr[x].c=1;
}
}void up(int x){
tr[x].v=tr[x*2].v+tr[x*2+1].v;
tr[x].h=tr[x*2].h+tr[x*2+1].h;
}void cov(int x,int l,int r,int ql,int qr,ll z){
if(ql<=l&&r<=qr) dotag(x,l,r,0,0,0,z);
else{
int mid=l+r>>1;
dn(x,l,r);
if(ql<=mid) cov(x*2,l,mid,ql,qr,z);
if(mid<qr) cov(x*2+1,mid+1,r,ql,qr,z);
up(x);
}
}ll que(int x,int l,int r,int ql,int qr){
ll ans=0;
int mid=l+r>>1;
if(ql<=l&&r<=qr) return tr[x].h;
dn(x,l,r);
if(ql<=mid) ans=que(x*2,l,mid,ql,qr);
if(mid<qr) ans+=que(x*2+1,mid+1,r,ql,qr);
return ans;
}void build(int x,int l,int r){
int mid=l+r>>1;
tr[x].c=1;
if(l!=r){
build(x*2,l,mid);
build(x*2+1,mid+1,r);
up(x);
}
}
}
namespace xm{
struct QUE{
int l,r,i;
} que[100005];
ll ans[100005];
int a[100005],stk[100005];
void _(){
int N,Q;
scanf("%d%d",&N,&Q);
for(int i=1;i<=N;++i) scanf("%d",a+i);
for(int i=1;i<=Q;++i){
scanf("%d%d",&que[i].l,&que[i].r);
que[i].i=i;
}
std::sort(que+1,que+Q+1,[](QUE a,QUE b){return a.r<b.r;});
segt::build(1,1,N);
int qi=1;
for(int i=1;i<=N;++i){
while(*stk&&a[stk[*stk]]>a[i]) --*stk;
segt::cov(1,1,N,stk[*stk]+1,i,a[i]);
stk[++*stk]=i;
segt::dotag(1,1,N,1,0,1,0);
for(;qi<=Q&&que[qi].r==i;++qi)
ans[que[qi].i]=segt::que(1,1,N,que[qi].l,i);
}
for(int i=1;i<=Q;++i) printf("%lld\n",ans[i]);
}
}
int main(){
xm::_();
return 0;
}