题解：
虽然知道有点问题但是并没有debug出来
发现错误了。。相同元素的处理有错误
网上题解大都是分块。。（hn怎么道道分块）
用最普通的思路，可以枚举每个点作为最小值，向左向右延伸
但是多组询问显然我们是要去优化询问过程的
有一种方法就是先找出最大值
（其实也可以是随意一个位置吧，但yy一下应该最大值能扩展的比较快）
然后向两边分别找第一个比它小的值
那么我们会发现，中间这一段元素他们一定是小于两边的值的
也就是说，如果这两个点在区间里，中间的点也全部在区间里
那么就可以用前缀和来预处理了
当比它小的点已经超出边界的时候，显然是可以递归处理的
查找最大值用倍增维护一下（线段树多了个log）
时间复杂度在数据不随机的情况下大概会炸的
并没有ac的代码：
#include <bits/stdc++.h>
using namespace std;
#define maxn 100100
#define INF 1e9
#define ll long long
ll h,t,n,m;
ll v[maxn],dp1[maxn],dp2[maxn],sum[maxn];
struct re{
ll h,t,pos,x;
}p[maxn*];
struct ree{
ll x1,x2;
}bz1[][maxn];
ll pd1(ll x,ll y)
{
if (v[x]>=v[y]) return(y);
else return(pd1(x,dp1[y]));
}
ll pd2(ll x,ll y)
{
if (v[x]>=v[y]) return(y);
else return(pd2(x,dp2[y]));
}
void updata(ll x)
{
p[x].x=max(p[x*].x,p[x*+].x);
if (p[x*].x>p[x*+].x)
p[x].pos=p[x*].pos;
else p[x].pos=p[x*+].pos;
}
int query(int h,int t)
{
int x=log2(t-h+),ans;
ree a=bz1[x][h],b=bz1[x][t-(<<x)+];
if (a.x1<b.x1) ans=b.x2; else ans=a.x2;
return(ans);
}
ll js(ll x,ll h,ll t)
{
return(v[x]*(min(dp2[x],t+)-x)*(x-max(dp1[x],h-)));
}
ll queryall(ll h,ll t)
{
if (h>t) return();
ll ans=,tmp,x;
tmp=x=query(h,t);
ans+=js(x,h,t);
while (dp2[x]<=t)
{
ans+=sum[dp2[x]-]-sum[x];
x=dp2[x];
ans+=js(x,h,t);
}
ans+=queryall(x+,t); x=tmp;
while (dp1[x]>=h)
{
ans+=sum[x-]-sum[dp1[x]];
x=dp1[x];
ans+=js(x,h,t);
}
ans+=queryall(h,x-);
return(ans);
}
int main()
{
freopen("noip.in","r",stdin);
freopen("noip.out","w",stdout);
std::ios::sync_with_stdio(false);
cin>>n>>m;
v[]=-INF; v[n+]=-INF;
for (ll i=;i<=n;i++) cin>>v[i];
for (ll i=;i<=n;i++)
{
dp1[i]=pd1(i,i-);
}
for (ll i=n;i>=;i--)
{
dp2[i]=pd2(i,i+);
}
for (int i=;i<=n;i++)
bz1[][i].x1=v[i],bz1[][i].x2=i;
for (int i=;i<=;i++)
for (int j=;j<=n;j++)
if (j+(<<i)-<=n)
{
ree a=bz1[i-][j],b=bz1[i-][j+(<<(i-))];
if (a.x1>b.x1) bz1[i][j].x1=a.x1,bz1[i][j].x2=a.x2;
else bz1[i][j].x2=b.x1,bz1[i][j].x2=b.x2;
}
for (ll i=;i<=n;i++)
{
sum[i]=
sum[i-]+(i-dp1[i])*(dp2[i]-i)*v[i];
}
for (ll i=;i<=m;i++)
{
cin>>h>>t;
cout<<queryall(h,t)<<endl;
}
}