题意
给一个长度为 \(n\) 的序列 \(a\)，和两个值 \(p1,p2\)。
一个点对 \((x,y)\) 的权值为：
- \(a_x,a_y\) 为区间 \([x,y]\) 最大值和次大值：\(p1\)。
- \(a_x,a_y\) 其中一个是区间 \([x,y]\) 的最大值，令一个不是 \([x,y]\) 次大值：\(p2\)。
- 其祂情况：0。
有 \(m\) 次询问 \((l,r)\)，求所有满足 \(l\le x<y\le r\) 的点对 \((x,y)\) 的权值和。
\(n,m\le2\times10^5,p1,p2\le1000\)。
思路
对于每个 \(i\)，求出祂前面第一个比祂大的 \(l\) 和后面第一个比祂大的 \(r\)，那么点对 \((l,r)\)，权值为 \(p1\)，点对 \((l,i+1),(l,i+2),\dots,(l,r-1)\) 的权值为 \(p2\)，点对 \((l+1,r),(l+2,r),\dots,(i-1,r)\) 的权值为 \(p2\)。
这是一个二维的问题，考虑离线下来用扫描线加线段树，最后要把相邻两个点的贡献加上，祂们的权值都是 \(p1\)，但是上面的方法统计不到。
代码
/*
Luogu P3722 [AHOI2017/HNOI2017] 影魔
2026-04-15
*/
#include<bits/stdc++.h>
using namespace std;
namespace IO{template<typename T>inline void read(T&x){x=0;char c=getchar();bool f=0;while(!isdigit(c)) c=='-'?f=1:0,c=getchar();while(isdigit(c)) x=x*10+c-'0',c=getchar();f?x=-x:0;}template<typename T>inline void write(T x){if(x==0){putchar('0');return ;}x<0?x=-x,putchar('-'):0;short st[50],top=0;while(x) st[++top]=x%10,x/=10;while(top) putchar(st[top--]+'0');}inline void read(char&c){c=getchar();while(isspace(c)) c=getchar();}inline void write(char c){putchar(c);}inline void read(string&s){s.clear();char c;read(c);while(!isspace(c)&&~c) s+=c,c=getchar();}inline void write(string s){for(int i=0,len=s.size();i<len;i++) putchar(s[i]);}template<typename T>inline void write(T*x){while(*x) putchar(*(x++));}template<typename T,typename...T2> inline void read(T&x,T2&...y){read(x),read(y...);}template<typename T,typename...T2> inline void write(const T x,const T2...y){write(x),putchar(' '),write(y...),sizeof...(y)==1?putchar('\n'):0;}
}using namespace IO;
#define LL long long
const int maxn=200010,inf=1000000000;
int n,m,p1,p2,L[maxn],R[maxn],a[maxn],cnt_q;
LL ans[maxn];
vector<int>st;
class Sgement_Tree{
private:struct node{LL sum,lan;}t[maxn*4];void add_tag(int u,int add,int l,int r){t[u].sum+=1ll*(r-l+1)*add;t[u].lan+=add;}void down(int u,int l,int r){int mid=l+r>>1;add_tag(u<<1,t[u].lan,l,mid),add_tag(u<<1|1,t[u].lan,mid+1,r);t[u].lan=0;}void update(int u,int l,int r,int ll,int rr,int z){if(l>rr||r<ll) return ;if(ll<=l&&r<=rr) return add_tag(u,z,l,r);down(u,l,r);int mid=l+r>>1;update(u<<1,l,mid,ll,rr,z),update(u<<1|1,mid+1,r,ll,rr,z);t[u].sum=t[u<<1].sum+t[u<<1|1].sum;}LL query(int u,int l,int r,int ll,int rr){if(l>rr||r<ll) return 0;if(ll<=l&&r<=rr) return t[u].sum;down(u,l,r);int mid=l+r>>1;return query(u<<1,l,mid,ll,rr)+query(u<<1|1,mid+1,r,ll,rr);}
public:void update(int l,int r,int z){update(1,1,n,l,r,z);}LL query(int l,int r){return query(1,1,n,l,r);}
}t;
struct node{int w,type,l,r,xs,id;auto operator<=>(const node&other) const=default;
}q[maxn*10];
signed main(){read(n,m,p1,p2);for(int i=1;i<=n;i++) read(a[i]),R[i]=n+1;a[0]=a[n+1]=inf;st.push_back(0);for(int i=1;i<=n;i++){while(a[i]>a[st.back()]) R[st.back()]=i,st.pop_back();L[i]=st.back();st.push_back(i);}for(int i=1;i<=m;i++){int l,r;read(l,r);q[++cnt_q]={l-1,1,l,r,-1,i};q[++cnt_q]={r,1,l,r,1,i};ans[i]=1ll*(r-l)*p1;}for(int i=1;i<=n;i++){int l=L[i],r=R[i];if(l>=1&&r<=n) q[++cnt_q]={r,0,l,l,p1,0};if(r<=n&&i>l+1) q[++cnt_q]={r,0,l+1,i-1,p2,0};if(l>=1&&r>i+1) q[++cnt_q]={l,0,i+1,r-1,p2,0};}sort(q+1,q+1+cnt_q);for(int i=1;i<=cnt_q;i++){auto[w,tp,l,r,z,id]=q[i];if(tp==1) ans[id]+=z*t.query(l,r);else t.update(l,r,z);}for(int i=1;i<=m;i++) write(ans[i]),write("\n");return 0;
}