10pts求条玄关

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100050;
int a[N],aft[N];
struct que{
	int l,r,id;
	ll ans;
};
que q[N];
bool cmp(que x,que y){
	if(x.r==y.r)return x.l<y.l;
	return x.r<y.r;
}
bool bk(que x,que y){
	return x.id<y.id;
}
struct sgt{
	int l,r;
	ll num,hdel;//hdel为历史和与当前版本的差值，hsum=hdel+t*num
	ll tg; 
};
sgt s[N*4];
void pup(int tt){
	s[tt].num=s[tt*2].num+s[tt*2+1].num;
	s[tt].hdel=s[tt*2].hdel+s[tt*2+1].hdel;
	return ;
}
void pdown(int tt,int t){
	if(s[tt].tg==0)return ;
	s[tt*2].tg+=s[tt].tg;
	s[tt*2+1].tg+=s[tt].tg;
	ll del1,del2;
	del1=s[tt].tg*(s[tt*2].r-s[tt*2].l+1)-s[tt*2].num;
	s[tt*2].num+=del1;
	s[tt*2].hdel-=(ll)(t-1)*del1;
	del2=s[tt].tg*(s[tt*2+1].r-s[tt*2+1].l+1)-s[tt*2+1].num;
	s[tt*2+1].num+=del2;
	s[tt*2+1].hdel-=(ll)(t-1)*del2;
	s[tt].tg=0;
	return ;
}
void build(int l,int r,int tt){
	s[tt].l=l,s[tt].r=r;
	if(l==r)return ;
	int mid=(l+r)/2;
	build(l,mid,tt*2);
	build(mid+1,r,tt*2+1);
	pup(tt);
	return ; 
}
void cov(int l,int r,int tt,int k,int t){ 
	if(l<=s[tt].l&&s[tt].r<=r){
		ll del=(ll)k*(s[tt].r-s[tt].l+1)-s[tt].num;
		s[tt].num+=del;
		s[tt].hdel-=(ll)(t-1)*del;
		s[tt].tg=k;
		return ;
	}
	pdown(tt,t);
	int mid=(s[tt].l+s[tt].r)/2;
	if(l<=mid)cov(l,r,tt*2,k,t);
	if(mid<r)cov(l,r,tt*2+1,k,t);
	pup(tt);
	return ;
}
ll ask_num(int l,int r,int tt,int t){
	if(l<=s[tt].l&&s[tt].r<=r)return s[tt].num;
	pdown(tt,t);
	int mid=(s[tt].l+s[tt].r)/2;
	ll ans=0;
	if(l<=mid)ans+=ask_num(l,r,tt*2,t);
	if(mid<r)ans+=ask_num(l,r,tt*2+1,t);
	return ans;
}
ll ask_hdel(int l,int r,int tt,int t){
	if(l<=s[tt].l&&s[tt].r<=r)return s[tt].hdel;
	pdown(tt,t);
	int mid=(s[tt].l+s[tt].r)/2;
	ll ans=0;
	if(l<=mid)ans+=ask_hdel(l,r,tt*2,t);
	if(mid<r)ans+=ask_hdel(l,r,tt*2+1,t);
	return ans;
}
stack<int>st;
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	build(1,n,1);
	for(int i=1;i<=n;i++){
		while(st.size()&&a[st.top()]>a[i])st.pop();
		if(st.size())aft[i]=st.top()+1;
		else aft[i]=1;
		st.push(i);
	}
	for(int i=1;i<=m;i++){
		scanf("%d%d",&q[i].l,&q[i].r);
		q[i].id=i,q[i].ans=0;
	}
	sort(q+1,q+m+1,cmp);
	int tp=1;
	for(int i=1;i<=n;i++){
		cov(aft[i],i,1,a[i],i);
		while(q[tp].r==i){
			q[tp].ans=(ll)i*ask_num(q[tp].l,q[tp].r,1,i)+ask_hdel(q[tp].l,q[tp].r,1,i);
			tp++;
		}
		int pjsk=ask_num(1,1,1,i);
	}
	sort(q+1,q+m+1,bk);
	for(int i=1;i<=m;i++)printf("%lld\n",q[i].ans);
	return 0;
}