影魔
- 这么简单的方法尽然想不到，我是真的菜
- 对每个点，用单调栈的方式处理出他左右第一个比他大的数的位置，你可以把\(0\)和\(n+1\)设成\(inf\)。
- 显然对于每对\(lef[i]\)和\(rig[i]\)都会做出\(p1\)的贡献
- 每个\(lef[i]\)会对\(i+1\)到\(rig[i]-1\)做出\(p2\)贡献
- 同理，每个\(rig[i]\)都会给\(lef[i]+1\)到\(i-1\)做出\(p2\)贡献
- 用结构体存下来，按顺序用线段树将贡献加入即可
- 统计贡献，对于每个询问\(l-r\)在扫到\(l-1\)时将这段区间减去，在扫到\(r\)时再将这段区间贡献加上即可
// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
typedef int sign;
typedef long long ll;
#define For(i,a,b) for(register sign i=(sign)a;i<=(sign)b;++i)
#define Fordown(i,a,b) for(register sign i=(sign)a;i>=(sign)b;--i)
const int N=2e5+5;
bool cmax(sign &a,sign b){return (a<b)?a=b,1:0;}
bool cmin(sign &a,sign b){return (a>b)?a=b,1:0;}
template<typename T>inline T read()
{
T f=1,ans=0;
char ch=getchar();
while(!isdigit(ch)&&ch!='-')ch=getchar();
if(ch=='-')f=-1,ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch-'0'),ch=getchar();
return ans*f;
}
template<typename T>inline void write(T x,char y)
{
if(x==0)
{
putchar('0');putchar(y);
return;
}
if(x<0)
{
putchar('-');
x=-x;
}
static char wr[20];
int top=0;
for(;x;x/=10)wr[++top]=x%10+'0';
while(top)putchar(wr[top--]);
putchar(y);
}
void file()
{
#ifndef ONLINE_JUDGE
freopen("3722.in","r",stdin);
freopen("3722.out","w",stdout);
#endif
}
int n,m,p1,p2;
int a[N];
struct Q
{
int l,r,x,tag,id;
bool operator < (const Q &s)const {return x<s.x;}
}opt[N<<2];
int cnt;
ll ans[N];
void input()
{
int l,r;
n=read<int>();m=read<int>();p1=read<int>();p2=read<int>();
For(i,1,n)a[i]=read<int>();
For(i,1,m)
{
l=read<int>();r=read<int>();
ans[i]+=1ll*(r-l)*1ll*p1;
opt[++cnt]=(Q){l,r,l-1,-1,i};
opt[++cnt]=(Q){l,r,r,1,i};
}
}
const int inf=0x3f3f3f3f;
namespace Tree
{
#define mid ((l+r)>>1)
#define lson h<<1,l,mid
#define rson h<<1|1,mid+1,r
ll sum[N<<2],lazy[N<<2];
void push_up(int h)
{
sum[h]=sum[h<<1]+sum[h<<1|1];
}
void push_down(int h,int l,int r)
{
if(!lazy[h])return;
int ls=h<<1,rs=ls|1;
lazy[ls]+=lazy[h];lazy[rs]+=lazy[h];
sum[ls]+=lazy[h]*1ll*(mid-l+1);
sum[rs]+=lazy[h]*1ll*(r-mid);
lazy[h]=0;
}
void update(int h,int l,int r,int s,int t,ll v)
{
if(s<=l&&r<=t)
{
lazy[h]+=v;
sum[h]+=1ll*v*1ll*(r-l+1);
}
else
{
push_down(h,l,r);
if(s<=mid)update(lson,s,t,v);
if(mid<t)update(rson,s,t,v);
push_up(h);
}
}
ll query(int h,int l,int r,int s,int t)
{
if(s<=l&&r<=t)return sum[h];
push_down(h,l,r);
ll res=0;
if(s<=mid)res=query(lson,s,t);
if(mid<t)res+=query(rson,s,t);
push_up(h);
return res;
}
}
#define rg register
int lef[N],rig[N];
struct node
{
int l,r,x;
ll v;
bool operator < (const node &s)const {return x<s.x;}
}e[N<<2];
int sz;
void init()
{
int j;
sort(opt+1,opt+cnt+1);
a[0]=a[n+1]=inf;
For(i,1,n)
{
for(j=i-1;j>=0;j=lef[j])if(a[j]>a[i])break;
lef[i]=j;
}
Fordown(i,n,1)
{
for(j=i+1;j<=n+1;j=rig[j])if(a[j]>a[i])break;
rig[i]=j;
}
//For(i,1,n)cout<<lef[i]<<' '<<rig[i]<<endl;
For(i,1,n)
{
if(lef[i]+1<i&&rig[i]<=n)e[++sz]=(node){lef[i]+1,i-1,rig[i],p2};
if(1<=lef[i]&&rig[i]>i+1)e[++sz]=(node){i+1,rig[i]-1,lef[i],p2};
if(1<=lef[i]&&rig[i]<=n)e[++sz]=(node){lef[i],lef[i],rig[i],p1};
}
sort(e+1,e+sz+1);
}
void work()
{
int pos1=1,pos2=1;
while(pos2<=cnt&&!opt[pos2].x)pos2++;
//cerr<<pos2<<' '<<cnt<<endl;
For(i,1,n)
{
for(;pos1<=sz&&e[pos1].x==i;++pos1)
Tree::update(1,0,n,e[pos1].l,e[pos1].r,e[pos1].v);
for(;pos2<=cnt&&opt[pos2].x==i;++pos2)
ans[opt[pos2].id]+=Tree::query(1,0,n,opt[pos2].l,opt[pos2].r)*opt[pos2].tag;
}
For(i,1,m)write(ans[i],'\n');
}
int main()
{
file();
input();
init();
work();
return 0;
}