```cpp
/*
Author: EnderDeer
Online Judge: Luogu
*/
#include<bits/stdc++.h>
#define int long long
#define mem(x) memset(x,0,sizeof(x))
using namespace std;
int read(){
int s = 0,w = 1;
char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-')w = -1;ch = getchar();}
while(ch >= '0' && ch <= '9')s = s * 10 + ch - '0',ch = getchar();
return s * w;
}
struct node{
int l;
int r;
int id;
}q[1000010];
int n,m;
int a[1000010];
int ans[1000010];
int num[1000010];
int pre[1000010];
int nxt[1000010];
int l = 1,r,now;
int block;
int dp[1000010][30];
int f1[1000010];
int f2[1000010];
void initpre(){
for (int i = 1;i <= n;i ++){
int j = i - 1;
while(a[j] >= a[i] && j > 0)j = pre[j];
pre[i] = j;
}
for(int i = 1;i <= n;i ++)if(pre[i] == 0)pre[i] = i;
}
void initnxt(){
for (int i = n;i >= 1;i --){
int j = i + 1;
while(a[j] >= a[i] && j <= n)j = nxt[j];
nxt[i] = j;
}
for(int i = 1;i <= n;i ++)if(nxt[i] == n)nxt[i] = i;
}
void init(){
for (int i = 1;i <= n;i ++)dp[i][0] = a[i];
for (int j = 1;(1 << j) <= n;j ++){
for (int i = 1;i + (1 << j) - 1 <= n;i ++){
dp[i][j] = min(dp[i][j - 1],dp[i + (1 << (j - 1))][j - 1]);
}
}
}
int query(int x,int y){
int k = log2(y - x + 1);
return min(dp[x][k],dp[y - (1 << k) + 1][k]);
}
bool cmp(node x,node y){
return (num[x.l] ^ num[y.l]) ? num[x.l] < num[y.l] : ((num[x.l] & 1) ? x.r < y.r : x.r > y.r);
}
int mol(int x,int y){
int p = query(x - 1,y);
return a[p] * (y - p + 1) + f1[x - 1] - f1[p];
}
int mor(int x,int y){
int p = query(x,y + 1);
return a[p] * (p - x + 1) + f2[y + 1] - f2[p];
}
signed main(){
cin>>n>>m;
block = sqrt(n);
for(int i = 1;i <= n;i ++){
a[i] = read();
num[i] = (i - 1) / block + 1;
}
initpre();
initnxt();
init();
for(int i = 1;i <= n;i ++)f1[i] = f1[pre[i]] + a[i] * abs(i - pre[i]);
for(int i = n;i >= 1;i --)f2[i] = f2[nxt[i]] + a[i] * abs(nxt[i] - i);
for(int i = 1;i <= m;i ++){
q[i].l = read(),q[i].r = read();
q[i].id = i;
}
sort(q + 1,q + m + 1,cmp);
for(int i = 1;i <= m;i ++){
int ql = q[i].l;
int qr = q[i].r;
while(l < ql)now -= mol(++ l,r);
while(l > ql)now += mol(l --,r);
while(r < qr)now -= mor(l,r ++);
while(r > qr)now += mor(l,-- r);
ans[q[i].id] = now;
}
for(int i = 1;i <= m;i ++)cout<<ans[i]<<endl;
return 0;
}
```
by EDqwq @ 2021-02-28 18:08:26
@[林深时x见鹿](/user/294562) 简单说一下做法呗
by 天南星魔芋 @ 2021-02-28 19:07:31
对你的 initnxt 很不理解（调试时 $nxt$ 全为 $n+1$ ）
by 天南星魔芋 @ 2021-02-28 19:08:57
@[天南星魔芋](/user/399239) 参考第一篇题解
我知道我写的错漏百出
by EDqwq @ 2021-02-28 19:13:13
我看看~~别装弱了~~
by 天南星魔芋 @ 2021-02-28 19:14:20
@[天南星魔芋](/user/399239) 看完了吗
by EDqwq @ 2021-02-28 19:27:38
@[林深时x见鹿](/user/294562) 还没，我也很弱啊
不过你莫队右指针移动时+-搞反了
by 天南星魔芋 @ 2021-02-28 19:39:18
@[天南星魔芋](/user/399239) 改了，还是错了
by EDqwq @ 2021-02-28 19:55:24
@[林深时x见鹿](/user/294562) dp也错了
by 天南星魔芋 @ 2021-02-28 20:31:46
@[天南星魔芋](/user/399239) 求改一下
by EDqwq @ 2021-02-28 20:33:46