### 思路

#### 离线 / 莫队

$$f[l][r]=f[l][pre]+a[r]\times (r-pre)$$

$$a[p]\times(p-l+1)+f[p+1][r]$$

$$a[p] \times(p-l+1)+f[p+1][pre] + a[r]\times(r-pre)$$

\begin{aligned}f'[r]=&\sum_{l=1}^r f[l][r] \ =&f'[pre]+a[r]\times(r-pre)\end{aligned}

$a[p] \times(p-l+1)+f[r] – f[p]$

### 代码

#### 离线 / 莫队

#include <bits/stdc++.h>
#define ll long long
#define maxn 1000001
using namespace std;

int x=0,flag=1;char ch=getchar();
while(!isdigit(ch)&&ch!='-') ch=getchar();
if (ch=='-') flag=-1,ch=getchar();
while(isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*flag;
}

int n,a[maxn],q,len;
int p[20][maxn];
int pre[maxn],suf[maxn];
ll f_l[maxn],f_r[maxn];
ll ans[maxn],cur;

void init(){
for (int i=1;i<=n;++i)
p[0][i]=i;
for (int j=1;j<=19;++j)
for (int i=1;i<=n;++i)
if (i+(1<<j)-1<=n)
p[j][i]=(a[p[j-1][i]]<a[p[j-1][i+(1<<(j-1))]])?
p[j-1][i]:p[j-1][i+(1<<(j-1))];

int s[maxn],top=0;
for (int i=1;i<=n;++i){
while(top&&a[s[top]]>a[i])
suf[s[top--]]=i;
pre[i]=s[top],s[++top]=i;
}
while(top)
pre[s[top]]=s[top-1],
suf[s[top--]]=n+1;

for (int i=1;i<=n;++i)
f_r[i]=f_r[pre[i]]+1ll*a[i]*(i-pre[i]);
for (int i=n;i>=1;--i)
f_l[i]=f_l[suf[i]]+1ll*a[i]*(suf[i]-i);
}

int l,r,id;
l=a,r=b,id=c;
}
bool operator < (const Ask &x) const{
return l/len==x.l/len?r<x.r:l/len<x.l/len;
}
}T_T[maxn];

int Query(int l,int r){
int k=log(r-l+1.0)/log(2.0);
return (a[p[k][l]]<a[p[k][r-(1<<k)+1]])?
p[k][l]:p[k][r-(1<<k)+1];
}

ll Left(int L,int R){
int pos=Query(L,R);
return 1ll*a[pos]*(R-pos+1)+f_l[L]-f_l[pos];
}

ll Right(int L,int R){
int pos=Query(L,R);
return 1ll*a[pos]*(pos-L+1)+f_r[R]-f_r[pos];
}

int main(){
len=sqrt(n);
for (int i=1;i<=n;++i)
a[0]=a[n+1]=INT_MAX;
init();
for (int i=1;i<=q;++i){
}
sort(T_T+1,T_T+1+q);
int l=T_T[1].l,r=l-1;
for (int i=1;i<=q;++i){
int L=T_T[i].l,R=T_T[i].r;
while(l>L) cur+=Left(l-1,r),l--;
while(r<R) cur+=Right(l,r+1),r++;
while(l<L) cur-=Left(l,r),l++;
while(r>R) cur-=Right(l,r),r--;
ans[T_T[i].id]=cur;
}
for (int i=1;i<=q;++i)
printf("%lld\n",ans[i]);
return 0;
}

#### 在线

#include <bits/stdc++.h>
#define ll long long
#define maxn 100010
using namespace std;

int x=0,flag=1;char ch=getchar();
while(!isdigit(ch)&&ch!='-') ch=getchar();
if (ch=='-') flag=-1,ch=getchar();
while(isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*flag;
}

int n,a[maxn],q,len;
int p[20][maxn];
int pre[maxn],suf[maxn];
ll f_l[maxn],f_r[maxn];
ll g_l[maxn],g_r[maxn];
ll ans[maxn],cur;

void init(){
for (register int i=1;i<=n;++i)
p[0][i]=i;
for (register int j=1;j<=19;++j)
for (register int i=1;i<=n;++i)
if (i+(1<<j)-1<=n)
p[j][i]=(a[p[j-1][i]]<a[p[j-1][i+(1<<(j-1))]])?
p[j-1][i]:p[j-1][i+(1<<(j-1))];
else break;

int s[maxn],top=0;
for (register int i=1;i<=n;++i){
while(top&&a[s[top]]>a[i])
suf[s[top--]]=i;
pre[i]=s[top],s[++top]=i;
}
while(top)
pre[s[top]]=s[top-1],
suf[s[top--]]=n+1;

for (register int i=1;i<=n;++i)
f_r[i]=f_r[pre[i]]+1ll*a[i]*(i-pre[i]),
g_r[i]=g_r[i-1]+f_r[i];
for (register int i=n;i>=1;--i)
f_l[i]=f_l[suf[i]]+1ll*a[i]*(suf[i]-i),
g_l[i]=g_l[i+1]+f_l[i];
}

inline int Query(int l,int r){
int k=log(r-l+1.0)/log(2.0);
return (a[p[k][l]]<a[p[k][r-(1<<k)+1]])?
p[k][l]:p[k][r-(1<<k)+1];
}

void print(ll x){
if (!x) return;
print(x/10);
putchar('0'+x%10);
}

ll solve(int l,int r){
int p=Query(l,r);
ll res=1ll*a[p]*(r-p+1)*(p-l+1);
res+=g_r[r]-g_r[p]-f_r[p]*(r-p);
res+=g_l[l]-g_l[p]-f_l[p]*(p-l);
return res;
}

int main(){
len=sqrt(n);
for (register int i=1;i<=n;++i)
a[0]=a[n+1]=INT_MAX;
init();
for (register int i=1;i<=q;++i){
}