题意分析
$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 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
//#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;
}
