90分求调（TLE #2）

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define F(i,a,b) for(int i=a;i<=b;i++)
#define DF(i,a,b) for(int i=a;i>=b;i--)

int read(){int x=0,f=0;char ch=getchar();while(ch<48||ch>57){f|=(ch=='-');ch=getchar();}while(ch>=48&&ch<=57){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return f?-x:x;}
void write(int x){int _num=0;char ch[101];if(x<0){x=-x;putchar('-');}do{ch[++_num]=x%10+48;x/=10;}while(x>0);for(;_num;){putchar(ch[_num--]);}}

struct node{
	int l,r,maxn,maxi,ll,rr,lsum,rsum;
}tree[800051],atree[10000051];
int n,m,p,pp,treenum;
int a[200051],lmax[200051],rmax[200051];

void firstbuild()
{
	F(i,2,n)
	{
		if(a[i-1]>a[i])
		{
			lmax[i]=i-1;
		}
		else
		{
			int j=i-1;
			while(a[lmax[j]]<a[i]&&lmax[j]!=0)
			{
				j=lmax[j];
			}
			lmax[i]=lmax[j];
		}
	}
	rmax[n]=n+1;
	DF(i,n-1,1)
	{
		if(a[i+1]>a[i])
		{
			rmax[i]=i+1;
		}
		else
		{
			int j=i+1;
			while(a[rmax[j]]<a[i]&&rmax[j]!=n+1)
			{
				j=rmax[j];
			}
			rmax[i]=rmax[j];
		}
	}
}

void build(int now,int l,int r)
{
	tree[now].l=l,tree[now].r=r;
	if(l==r)
	{
		tree[now].maxn=a[l];
		tree[now].maxi=l;
		return ;
	}
	int mid=(l+r)>>1;
	build(now<<1,l,mid);
	build(now<<1|1,mid+1,r);
	if(tree[now<<1].maxn>tree[now<<1|1].maxn)
	{
		tree[now].maxn=tree[now<<1].maxn;
		tree[now].maxi=tree[now<<1].maxi;
	}
	else
	{
		tree[now].maxn=tree[now<<1|1].maxn;
		tree[now].maxi=tree[now<<1|1].maxi;
	}
}
int qmax(int now,int l,int r)
{
	if(tree[now].l>=l&&tree[now].r<=r)
	{
		return tree[now].maxi;
	}
	int mid=(tree[now].l+tree[now].r)>>1,x=0,y=0;
	if(l<=mid)
	{
		x=qmax(now<<1,l,r);
	}
	if(r>mid)
	{
		y=qmax(now<<1|1,l,r);
	}
	if(a[x]>a[y])
	{
		return x;
	}
	return y;
}

void rebuild(int now,int l,int r)
{
	atree[now].l=l,atree[now].r=r;
	if(l==r)
	{
		return ;
	}
	atree[now].maxi=qmax(1,l,r);
	if(atree[now].maxi>l)
	{
		int j=atree[now].maxi-1;
		while(j>l-1)
		{
			atree[now].lsum+=p;
			atree[now].lsum+=(j-lmax[j]-1)*pp;
			j=lmax[j];
		}
		atree[now].maxn+=atree[now].lsum;
		if(l<atree[now].maxi-1)
		{
			atree[now].ll=++treenum;
			rebuild(treenum,l,atree[now].maxi-1);
			atree[now].maxn+=atree[atree[now].ll].maxn;
		}
	}
	if(atree[now].maxi<r)
	{
		int j=atree[now].maxi+1;
		while(j<r+1)
		{
			atree[now].rsum+=p;
			atree[now].rsum+=(rmax[j]-j-1)*pp;
			j=rmax[j];
		}
		atree[now].maxn+=atree[now].rsum;
		if(r>atree[now].maxi+1)
		{
			atree[now].rr=++treenum;
			rebuild(treenum,atree[now].maxi+1,r);
			atree[now].maxn+=atree[atree[now].rr].maxn;
		}
	}
}
int amax(int now,int l,int r)
{
	if(atree[now].l>=l&&atree[now].r<=r)
	{
		return atree[now].maxn;
	}
	int sum=0;
	if(atree[now].maxi>r)
	{
		if(atree[now].maxi>atree[now].l+1)
		{
			return amax(atree[now].ll,l,r);
		}
		else
		{
			return 0;
		}
	}
	if(atree[now].maxi<l)
	{
		if(atree[now].maxi<atree[now].r-1)
		{
			return amax(atree[now].rr,l,r);
		}
		else
		{
			return 0;
		}
	}
	if(atree[now].maxi>max(atree[now].l,l))
	{
		int j=atree[now].maxi-1;
		if(atree[now].l>=l)
		{
			sum+=atree[now].lsum;
		}
		else
		{
			sum+=p;
			while(lmax[j]>=l)
			{
				sum+=p;
				sum+=(j-lmax[j]-1)*pp;
				j=lmax[j];
			}
			sum+=(j-l)*pp;
		}
		if(atree[now].l<atree[now].maxi-1)
		{
			sum+=amax(atree[now].ll,l,r);
		}
	}
	if(atree[now].maxi<min(atree[now].r,r))
	{
		int j=atree[now].maxi+1;
		if(atree[now].r<=r)
		{
			sum+=atree[now].rsum;
		}
		else
		{
			sum+=p;
			while(rmax[j]<=r)
			{
				sum+=p;
				sum+=(rmax[j]-j-1)*pp;
				j=rmax[j];
			}
			sum+=(r-j)*pp;
		}
		if(atree[now].r>atree[now].maxi+1)
		{
			sum+=amax(atree[now].rr,l,r);
		}
	}
	return sum;
}

signed main()
{
	n=read(),m=read(),p=read(),pp=read();
	F(i,1,n)
	{
		a[i]=read();
	}
	firstbuild();
	build(1,1,n);
	treenum=1;
	rebuild(1,1,n);
	F(i,1,m)
	{
		int x=read(),y=read();
		write(amax(1,x,y));
		putchar('\n');
	}
	return 0;
}