设(l[i])为i左边第一个比i大的数的下标。(r[i])为i右边第一个比i大的数的下标。
我们把(p1,p2)分开考虑。
当产生贡献为(p1)时(i)和(j)一定满足，分别为(l[x],r[x])枚举每一个值为(i)，(j)之间最大值可证。
党产生贡献为(p2)时(i)和(j)满足分别为(l[x],[x+1,r[x]-1])或([l[x]+1,x-1],r[x])，此时(a[x])为(i)，(j)之间最大值，(i)，(j)一个比(a[x])大，一个比(a[x])小。
然后就把问题转化为二维数点问题。产生贡献的点对对应坐标系中的一个点（为了避免重复计数如((r[x],l[x]))和((l[x],r[x]))，可以把小的作为横坐标，大的作为纵坐标）。然后我们每一次询问就是横坐标在([l,r])之间，纵坐标在([l,r])之间的权值和。
然后就可以用主席树做了。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
#define int long long
const int N=201000;
struct line{ int l,r,w; };
vector<line> vec[N];
int tot,root[N],lazy[N*70],ch[N*70][2],sum[N*70];
int n,m,p1,p2,a[N],stack[N],top,l[N],r[N];
void add(int l,int r,int L,int R,int w,int pre,int &now){
now=++tot;
ch[now][0]=ch[pre][0];
ch[now][1]=ch[pre][1];
lazy[now]=lazy[pre];
sum[now]=sum[pre]+(R-L+1)*w;
if(l==L&&r==R){
lazy[now]+=w;
return;
}
int mid=(l+r)>>1;
if(L>mid)add(mid+1,r,L,R,w,ch[pre][1],ch[now][1]);
else if(R<=mid)add(l,mid,L,R,w,ch[pre][0],ch[now][0]);
else{
add(l,mid,L,mid,w,ch[pre][0],ch[now][0]);
add(mid+1,r,mid+1,R,w,ch[pre][1],ch[now][1]);
}
}
int check(int l,int r,int L,int R,int pre,int now){
if(l==L&&r==R)return sum[now]-sum[pre];
int mid=(l+r)>>1;
if(L>mid)return (lazy[now]-lazy[pre])*(R-L+1)+check(mid+1,r,L,R,ch[pre][1],ch[now][1]);
else if(R<=mid)return (lazy[now]-lazy[pre])*(R-L+1)+check(l,mid,L,R,ch[pre][0],ch[now][0]);
else return (lazy[now]-lazy[pre])*(R-L+1)
+check(l,mid,L,mid,ch[pre][0],ch[now][0])
+check(mid+1,r,mid+1,R,ch[pre][1],ch[now][1]);
}
int read(){
int sum=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){sum=sum*10+ch-'0';ch=getchar();}
return sum*f;
}
signed main(){
n=read(),m=read(),p1=read(),p2=read();
for(int i=1;i<=n;i++)a[i]=read();
for(int i=1;i<=n;i++){
while(a[i]>a[stack[top]]&&top)r[stack[top--]]=i;
stack[++top]=i;
}
while(top)r[stack[top--]]=n+1;
for(int i=n;i>=1;i--){
while(a[i]>a[stack[top]]&&top)l[stack[top--]]=i;
stack[++top]=i;
}
while(top)l[stack[top--]]=0;
for(int i=1;i<=n;i++){
line x;
if(i!=n&&i+1<=r[i]-1){
x.l=i+1;x.r=r[i]-1;x.w=p2;
vec[l[i]].push_back(x);
}
if(l[i]+1<=i-1&&i!=1){
x.l=l[i]+1;x.r=i-1;x.w=p2;
vec[r[i]].push_back(x);
}
x.l=i;x.r=i;x.w=p1;
vec[l[i]].push_back(x);
vec[r[i]].push_back(x);
}
for(int i=1;i<=n;i++){
root[i]=root[i-1];
for(int j=0;j<vec[i].size();j++)
add(1,n,vec[i][j].l,vec[i][j].r,vec[i][j].w,root[i],root[i]);
}
for(int i=1;i<=m;i++){
int l=read(),r=read();
printf("%lld
",check(1,n,l,r,root[l-1],root[r]));
}
return 0;
}