Part1
先想暴力，对于每次询问，可以直接 \(\Theta(n^2)\) 枚举数对，用 \(ST\)表 判断一下，复杂度为 \(\Theta(qn^2)\)。
发现枚举数对没有前途，考虑 \((i,j)\) 之间的最大值，发现一个数对产生的贡献只和区间的最大值有关，我们从这个最大值入手。我们把一个数对的贡献看做其区间最大值的贡献，那么对于给定的区间，总的贡献就是区间内每个数贡献的加和，又注意到这是个排列，所以不用考虑相同数的影响。
设 \(L_i\) 表示在 \(i\) 左侧第一个大于 \(k_i\) 的值的位置，\(R_i\) 为类似的定义。那么显然 \(k_i\) 就是区间 \([L_i+1,R_i-1]\) 的最大值，那么数对 \((L_i,R_i)\) 就会产生一个 \(p_1\) 的贡献。区间 \([\max(L_i+1,l),i-1]\) 的值都会和 \(R_i\) 产生 \(p_2\) 的贡献，类似的，区间 \([i+1,\min(R_i-1,r)]\) 的值都会和 \(L_i\) 产生 \(p_2\) 的贡献，这个显然。相邻的两个数也会产生 \(p_1\) 的贡献，这个也显然。
那么直接枚举每个数，计算上述的贡献，再加和就行了，这样直接做是 \(\Theta(qn)\) 的。
Part2
考虑优化上述的算法，我们现在要统计的就是区间有多少数的 \(L_i\) 和 \(R_i\) 都在区间内，还有每个三元组 \((L_i,i,R_i)\) 产生的贡献。把这想象成一个二维平面，那么就可以看做一个二维数点问题，贡献看做是二维平面内的线或者点。
在线做的话直接上主席树就好了，需要维护区间修改，区间求和。直接永久化标记就行了。
最后别忘了相邻的数的贡献。
时间复杂度为 \(\Theta(q\log n)\)。
Code
#include <iostream>
#include <cstdio>
#include <vector>
#define int long long
const int N=2e5+10;
using namespace std;
inline int read() {
int f=1, x=0;
char ch=getchar();
while(ch>'9' || ch<'0') {
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0' && ch<='9') {
x=(x<<3)+(x<<1)+(ch^48);
ch=getchar();
}
return f*x;
}
inline void write(int x) {
cout<<x; putchar('\n');
}
int n, m, p1, p2;
int a[N], L[N], R[N], sta[N];
struct node {
int l, r, w;
};
vector <node> p[N];
int root[N];
struct Seg_Tree {
#define ls(k) t[k].ls
#define rs(k) t[k].rs
int cnt_root;
struct Tree {
int sum, ls, rs, tag;
}t[N*120];
inline int clone(int k) {
cnt_root++;
t[cnt_root]=t[k];
return cnt_root;
}
int up_date(int k,int l,int r,int L,int R,int val) {
k=clone(k);
t[k].sum+=(R-L+1)*val;
if(L==l && r==R) {
t[k].tag+=val;
return k;
}
int mid=(l+r)>>1;
if(L>mid) rs(k)=up_date(rs(k), mid+1, r, L, R, val);
else if(R<=mid) ls(k)=up_date(ls(k), l, mid, L, R, val);
else {
ls(k)=up_date(ls(k), l, mid, L, mid, val);
rs(k)=up_date(rs(k), mid+1, r, mid+1, R, val);
}
return k;
}
int query(int u,int v,int l,int r,int L,int R) {
if(L==l && r==R) return t[v].sum-t[u].sum;
int mid=(l+r)>>1, sum=(t[v].tag-t[u].tag)*(R-L+1);
if(L>mid) return sum+query(rs(u), rs(v), mid+1, r, L, R);
else if(R<=mid) return sum+query(ls(u), ls(v), l, mid, L, R);
else return sum+query(ls(u), ls(v), l, mid, L, mid)+
query(rs(u), rs(v), mid+1, r, mid+1, R);
}
#undef ls
#undef rs
}T;
signed main() {
n=read(), m=read(), p1=read(), p2=read();
for(int i=1;i<=n;i++) {
a[i]=read();
}
int top=0;
fill(R+1, R+n+1, n+1);
for(int i=1;i<=n;i++) {
while(top && a[i]>a[sta[top]]) {
R[sta[top]]=i;
top--;
}
L[i]=sta[top];
sta[++top]=i;
}
for(int i=1;i<=n;i++) {
if(i!=n && i+1<=R[i]-1) p[L[i]].emplace_back((node){i+1, R[i]-1, p2});
if(L[i]+1<=i-1 && i!=1) p[R[i]].emplace_back((node){L[i]+1, i-1, p2});
if(L[i]!=0 && R[i]!=n+1) p[R[i]].emplace_back((node){L[i], L[i], p1});
}
for(int i=1;i<=n;i++) {
root[i]=root[i-1];
for(int j=0;j<(int)p[i].size();j++) {
node now=p[i][j];
root[i]=T.up_date(root[i], 1, n ,now.l, now.r, now.w);
}
}
for(int i=1;i<=m;i++) {
int l=read(), r=read();
int ans=T.query(root[l-1], root[r], 1, n, l, r);
ans+=p1*(r-l);
write(ans);
}
return 0;
}