题目传送门
题意分析
\(p_1,p_2\) 无关，分开计算贡献是显然的。
考虑如何刻画贡献。
记询问区间为 \([l,r]\)，原序列为 \(a_1,a_2,\cdots,a_n\)。
那么：
-
\((i,j)\) 产生 \(p_1\) 贡献当且仅当（和 \(j=i+1\) 时恒有 \(p_1\) 贡献）：
\[\max_{k=i+1}^{j-1}a_k<\min(a_i,a_j) \] -
\((i,j)\) 产生 \(p_2\) 贡献有两种方式：
\[\begin{aligned} a_i<&\max_{i=i+1}^{j-1}<a_j\\ a_j<&\max_{i=i+1}^{j-1}<a_i\\ \end{aligned} \]
设 \(a_x\) 为 \(a_{i+1},a_{i+2},\cdots,a_{j-1}\) 中的最大值，则三种贡献都与 \(x\) 有关。
发现通过 \((i,j)\) 找 \(x\) 不能优化，正难则反，考虑通过 \(x\) 统计 \((i,j)\) 的贡献。
设 \(L_i,R_i\) 分别为 \(i\) 左边、右边的第一个大于 \(a_i\) 的位置。若不存在，则钦定 \(L_i=0\) 或 \(R_i=n+1\)。
显然有 \(L_x\leq i<x<j\leq R_x\)，否则不满足 \(x\) 的定义。
-
对于 \(p_1\)：
又因为要产生 \(p_1\) 贡献，\(i\leq L_x\) 且 \(R_x\leq j\)。
联立不等式，解得 \((i,j)=(L_x,R_x)\)。
那么 \(x\) 对于 \([l,r]\) 的贡献便很好算的。
-
对于 \(p_2\)：
类似地联立不等式，可知：
- \(a_i<a_j\)，为 \(i\in[L_x+1,i-1],j=R_x\)。
- \(a_j<a_i\)，为 \(i=L_x,j\in[i+1,R_x-1]\)。
统计答案，可以扫描线，扫过 \(a_1,a_2,\cdots,a_n\) 的似乎后对应的在区间上加贡献。
同时扫描线统计 \([l,r]\) 答案即可。
AC 代码
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
typedef long long ll;
constexpr const int N=200000,M=200000;
struct question{int l,r,id,w;
};
vector<question>q[N+1];
int n,m,p1,p2,a[N+1],L[N+1],R[N+1];
vector<pair<int,int>>rL[N+1+1],lR[N+1];
ll ans[M+1];
struct segTree{struct node{int l,r;ll value,tag;int size(){return r-l+1;}}t[N<<2|1];void up(int p){t[p].value=t[p<<1].value+t[p<<1|1].value;}void build(int p,int l,int r){t[p]={l,r};if(l==r){return;}int mid=l+r>>1;build(p<<1,l,mid);build(p<<1|1,mid+1,r);up(p);}void down(int p){if(t[p].tag){t[p<<1].value+=1ll*t[p<<1].size()*t[p].tag;t[p<<1].tag+=t[p].tag;t[p<<1|1].value+=1ll*t[p<<1|1].size()*t[p].tag;t[p<<1|1].tag+=t[p].tag;t[p].tag=0;}}void add(int p,int l,int r,int k){if(l<=t[p].l&&t[p].r<=r){t[p].value+=1ll*t[p].size()*k;t[p].tag+=k;return;}down(p);if(l<=t[p<<1].r){add(p<<1,l,r,k);}if(t[p<<1|1].l<=r){add(p<<1|1,l,r,k);}up(p);}ll query(int p,int l,int r){if(l<=t[p].l&&t[p].r<=r){return t[p].value;}down(p);ll ans=0;if(l<=t[p<<1].r){ans=query(p<<1,l,r);}if(t[p<<1|1].l<=r){ans+=query(p<<1|1,l,r);}return ans;}
}t;
void pre(){vector<int>s;for(int i=1;i<=n;i++){while(s.size()&&a[s.back()]<=a[i]){s.pop_back();}if(s.size()){L[i]=s.back();}else{L[i]=0;}s.push_back(i);}s.resize(0);for(int i=n;1<=i;i--){while(s.size()&&a[s.back()]<=a[i]){s.pop_back();}if(s.size()){R[i]=s.back();}else{R[i]=n+1;}s.push_back(i);}for(int i=1;i<=n;i++){lR[L[i]].push_back({R[i],i});rL[R[i]].push_back({L[i],i});}
}
void solve(){t.build(1,0,n+1);for(int i=1;i<=n;i++){for(auto x:rL[i]){t.add(1,x.first,x.first,p1);}for(auto x:rL[i]){t.add(1,x.first+1,x.second-1,p2);}for(auto x:lR[i]){t.add(1,x.second+1,x.first-1,p2);}for(auto x:q[i]){ans[x.id]+=x.w*t.query(1,x.l,x.r);}}
}
int main(){/*freopen("test.in","r",stdin);freopen("test.out","w",stdout);*/ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n>>m>>p1>>p2;for(int i=1;i<=n;i++){cin>>a[i];}pre();for(int i=1;i<=m;i++){int l,r;cin>>l>>r;q[l-1].push_back({l,r,i,-1});q[r].push_back({l,r,i,1});ans[i]=1ll*(r-l)*p1;}solve();for(int i=1;i<=m;i++){cout<<ans[i]<<'\n';}cout.flush();/*fclose(stdin);fclose(stdout);*/return 0;
}