本来以为柯以打线段树，结果搜了题解，发现的确可以打，不过矩阵乘法是什么东西？？？

先打莫队吧。

对于这种区间的题，还是有目的的一个个来。

对于询问区间 $[l,r] $，如果变成了区间 $[l,r+1]$ ，那么增加的贡献应该是

$[l,r+1],[l+1,r+1],[l+2.r+1],\cdots,[r+1,r+1]$。

显然右端点是固定的，考虑如何$O(1)$求得这串贡献。

开个数组？记录贡献？

但是这个数组的范围很难确定，因为不知道这个区间最小的数，是否会超出区间。

为了解决这个问题，可以手动求一下，这个区间最小的数的位置$p$，之后它的贡献就是$[l\sim p,p]$

这个可以用ST表解决。

有了这个基础，意味着这个区间已经拥有一个断点$p$，也就是在求数组的时候会用到这个$p$，有助于理解。

那么$[p+1\sim r+1,r+1]$这段贡献，可以用类似前缀和的数组解决:

其中$pre_i$表示在$i$之前第一个比$i$小的数的位置，可以用单调栈求得，$sl$的意义为$[1sim l,l]的最小贡献。

for(int i=1;i<=n;i++)sl[i]=sl[pre[i]]+1ll*c[i]*(i-pre[i]);

这里其实可以发现一个问题，它不是线性继承的，意味着差分的时候不能乱差分。

上面求的$p$就发挥了很大的作用，因为它是这个区间最小的数，那么$sl[r]$一定是从$sl[p]$来的，它不能绕过去(否则$p$不是最小的)，所以$sl[r+1]-sl[p]$就是$[p+1\sim r+1,r+1]$的贡献。

$[l,r]->[l,r-1],[l,r]->[l+1,r],[l,r]->[l-1,r]$的情况与上面类似，就不一一列举了。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#define gc getchar()
#define ll long long
#define ld long double 
#define ull unsigned long long
using namespace std;
const int N=1e5+5,M=4e5+5;
template<class o>
inline void qr(o &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
template<class o>
void qw(o x)
{
    if(x<0)putchar('-'),x=-x;
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
ll sl[N],sr[N];
int bel[N],pre[N],nex[N],n,m,f[18][N],Log[N],c[N],sta[N];
inline int mmin(int x,int y){return c[x]>c[y]?y:x;}
void init()
{
    for(int i=2;i<=n;i++)Log[i]=Log[i>>1]+1;
    for(int i=1;i<=n;i++)f[0][i]=i;
    for(int i=1;i<=17;i++)
        for(int j=1;j+(1<<i)-1<=n;j++)
            f[i][j]=mmin(f[i-1][j],f[i-1][j+(1<<(i-1))]);
    int top=0;
    for(int i=1;i<=n;i++)
    {
        while(top&&c[sta[top]]>c[i])--top;
        pre[i]=sta[top];sta[++top]=i;
    }
    while(top)pre[sta[top]]=sta[top-1],--top;
    sta[top]=n+1;
    for(int i=n;i;i--)
    {
        while(top&&c[sta[top]]>c[i])--top;
        nex[i]=sta[top];sta[++top]=i;
    }
    while(top)nex[sta[top]]=sta[top-1],--top;
    for(int i=1;i<=n;i++)sl[i]=sl[pre[i]]+1ll*c[i]*(i-pre[i]);
    for(int i=n;i;i--)sr[i]=sr[nex[i]]+1ll*c[i]*(nex[i]-i);
}
inline int find(int a,int b)
{
    int k=Log[b-a+1];
    return mmin(f[k][a],f[k][b-(1<<k)+1]);
}
inline ll workr(int l,int r)
{
    int p=find(l,r);
    return 1ll*c[p]*(p-l+1)+sl[r]-sl[p];
}
inline ll workl(int l,int r)
{
    int p=find(l,r);
    return 1ll*c[p]*(r-p+1)+sr[l]-sr[p];
}
struct node{int l,r,id;}a[N];
ll Ans[N];
inline bool cmp(node a,node b){return bel[a.l]==bel[b.l]?a.r<b.r:bel[a.l]<bel[b.l];}
int main()
{
    qr(n),qr(m);
    for(int i=1;i<=n;i++)qr(c[i]);
    int sqr=sqrt(n),T=(n-1)/sqr+1;
    for(int i=1;i<=T;i++)
    {
        int L=(i-1)*sqr+1,R=min(L+sqr-1,n);
        for(int j=L;j<=R;j++)bel[j]=i;
    }
    init();
    for(int i=1;i<=m;i++)qr(a[i].l),qr(a[i].r),a[i].id=i;
    sort(a+1,a+m+1,cmp);int l=1,r=0;ll ans=0;
    for(int i=1;i<=m;i++)
    {
        int x=a[i].l,y=a[i].r;
        while(r<y)ans+=workr(l,++r);
        while(l>x)ans+=workl(--l,r);
        while(r>y)ans-=workr(l,r--);
        while(l<x)ans-=workl(l++,r);
        Ans[a[i].id]=ans;
    }
    for(int i=1;i<=m;i++)qw(Ans[i]),puts("");
    return 0;
}

线段树做法

适用性很广，便于理解。

首先一次询问的答案是 $\sum\limits_{i=l}^r\sum\limits_{j=i}^r\min\{C_k\}(k\in[i,j])$

假设现在记录到了$last$，记录一个 $val,sum$

$val_i=\min\{C_k\}(k\in[i,last])$，$sum_i$ 则记录历史版本的 $val_i$ 和，即

$sum_i=\sum\limits_{j=i}^{last}val_i=\sum\limits_{j=i}^{last}\min\{C_k\}(k\in[i,j])$

当$last$到了$r$时，上面的答案，其实就是$\sum\limits_{i=l}^r sum_i$

那么就可以用线段树维护 $val,sum $ ，只需要打四个标记 $(a,b,c,d)$ 。

即

$newsum=sum+val*c+d*(R-L+1)\\newval=val*a+b*(R-L+1)$

如果两个标记撞在一起，

列举一下 $val$ 的变化，

$a_2(a_1*val+b_1*(R-L+1))+b_2(R-L+1)=a_1a_2*val+b_1a_2*(R-L+1)+b_2*(R-L+1)$

对号入座，$a=a_1a_2,b=b_1a_2+b_2$

$c,d$也是如此。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#define gc getchar()
#define ll long long
#define ld long double 
#define ull unsigned long long
using namespace std;
const int N=1e5+5,M=4e5+5;
template<class o>
inline void qr(o &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
template<class o>
void qw(o x)
{
    if(x<0)putchar('-'),x=-x;
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
struct node
{
    ll a,b,c,d;
    node(ll a=1,ll b=0,ll c=0,ll d=0):a(a),b(b),c(c),d(d){}
    node operator +(const node y)const{return node(a*y.a,y.b+b*y.a,a*y.c+c,d+y.d+b*y.c);}
};
struct SGT{node w;ll v,s;int siz;}t[N<<2];
inline void update(int p)
{
    t[p].s=t[p<<1].s+t[p<<1|1].s;
    t[p].v=t[p<<1].v+t[p<<1|1].v;
}
inline void cw(int p,node w)
{
    t[p].s+=w.c*t[p].v+w.d*t[p].siz;
    t[p].v=w.a*t[p].v+w.b*t[p].siz;
    t[p].w=t[p].w+w;
}
void pushdown(int p)
{
    node w=t[p].w;
    if(w.a!=1||w.b||w.c||w.d)cw(p<<1,w),cw(p<<1|1,w),t[p].w=node(1,0,0,0);
}
void build(int p,int l,int r)
{
    t[p].siz=r-l+1;t[p].w=node(1,0,0,0);
    if(l==r){return ;}
    int mid=l+r>>1;
    build(p<<1,l,mid);build(p<<1|1,mid+1,r);
}
void change(int p,int l,int r,int L,int R,node w)
{
    if(L<=l&&R>=r){cw(p,w);return ;}
    int mid=l+r>>1;pushdown(p);
    if(L<=mid)change(p<<1,l,mid,L,R,w);
    if(R>mid)change(p<<1|1,mid+1,r,L,R,w);
    update(p);
}
ll query(int p,int l,int r,int L,int R)
{
    if(L<=l&&R>=r)return t[p].s;
    int mid=l+r>>1;pushdown(p);ll val=0;
    if(L<=mid)val+=query(p<<1,l,mid,L,R);
    if(R>mid)val+=query(p<<1|1,mid+1,r,L,R);
    return val;
}
struct Query{int l,r,id;}a[N];
inline bool cmp(Query a,Query b){return a.r==b.r?a.l<b.l:a.r<b.r;}
int sta[N],c[N],top;
ll ans[N];
int main()
{
    int n,m;qr(n),qr(m);
    for(int i=1;i<=n;i++)qr(c[i]);
    for(int i=1;i<=m;i++)qr(a[i].l),qr(a[i].r),a[i].id=i;
    sort(a+1,a+m+1,cmp);
    build(1,1,n);top=0;int j=1;
    for(int i=1;i<=n;i++)
    {
        while(top&&c[sta[top]]>c[i])--top;
        change(1,1,n,sta[top]+1,i,node(0,c[i],0,0));
        cw(1,node(1,0,1,0));sta[++top]=i;
        while(j<=m&&a[j].r==i)ans[a[j].id]=query(1,1,n,a[j].l,a[j].r),++j;
    }
    for(int i=1;i<=m;i++)qw(ans[i]),puts("");
    return 0;
}