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
|
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <stack>
#define MAXN (200000 + 5)
#define INF (0x7fffffff)
#define pii pair<int, int>
#define LL long long
#define LS(dq) ((dq) << 1)
#define RS(dq) (((dq) << 1) | 1)
using namespace std;
struct edg {
int le, ri;
LL zh, lazy;
} b[MAXN << 2];
struct question {
int le, ri, time, type, zh;
question() {}
question(int l, int r, int ti, int ty, int z) : le(l), ri(r), time(ti), type(ty), zh(z) {}
} que[MAXN << 2];
int n, q, cntq, a[MAXN], p1, p2, premax[MAXN], nexmax[MAXN];
LL ans[MAXN];
pii sq[MAXN];
void js(int dq, int le, int ri) {
b[dq].le = le, b[dq].ri = ri, b[dq].zh = b[dq].lazy = 0;
if (le == ri)
return;
int mi = (le + ri) >> 1;
js(LS(dq), le, mi), js(RS(dq), mi + 1, ri);
}
void push_down(int dq) {
LL x = b[dq].lazy;
b[LS(dq)].lazy += x, b[RS(dq)].lazy += x;
b[LS(dq)].zh += (b[LS(dq)].ri - b[LS(dq)].le + 1) * x;
b[RS(dq)].zh += (b[RS(dq)].ri - b[RS(dq)].le + 1) * x;
b[dq].lazy = 0;
}
LL cx(int dq, int le, int ri) {
if (le > b[dq].ri || le > ri || ri < b[dq].le)
return 0;
if (b[dq].le == le && b[dq].ri == ri)
return b[dq].zh;
if (b[dq].lazy)
push_down(dq);
int mi = (b[dq].le + b[dq].ri) >> 1;
if (le > mi)
return cx(RS(dq), le, ri);
else if (ri <= mi)
return cx(LS(dq), le, ri);
else
return cx(LS(dq), le, mi) + cx(RS(dq), mi + 1, ri);
}
void xg(int dq, int le, int ri, LL zh) {
if (le > b[dq].ri || le > ri || ri < b[dq].le)
return;
if (b[dq].le == le && b[dq].ri == ri) {
b[dq].lazy += zh;
b[dq].zh += (ri - le + 1) * zh;
return;
}
if (b[dq].lazy)
push_down(dq);
int mi = (b[dq].le + b[dq].ri) >> 1;
if (le > mi)
xg(RS(dq), le, ri, zh);
else if (ri <= mi)
xg(LS(dq), le, ri, zh);
else
xg(LS(dq), le, mi, zh), xg(RS(dq), mi + 1, ri, zh);
b[dq].zh = b[LS(dq)].zh + b[RS(dq)].zh;
}
bool cmp(const question& x, const question& y) {
if (x.time == y.time)
return x.type > y.type;
return x.time < y.time;
}
bool cmp2(const question& x, const question& y) {
if (x.time == y.time)
return x.type > y.type;
return x.time > y.time;
}
void solve() {
for (int i = 1; i <= n; i++) {
que[++cntq] = question(premax[i], premax[i], nexmax[i], 1, p1);
que[++cntq] = question(premax[i] + 1, i - 1, nexmax[i], 1, p2);
}
for (int i = 1; i <= q; i++) que[++cntq] = question(sq[i].first, n, sq[i].second, 0, i);
sort(que + 1, que + cntq + 1, cmp);
js(1, 1, n);
for (int i = 1; i <= cntq; i++)
if (que[i].type)
xg(1, que[i].le, que[i].ri, que[i].zh);
else
ans[que[i].zh] += cx(1, que[i].le, que[i].ri);
cntq = 0;
for (int i = 1; i <= n; i++) que[++cntq] = question(i + 1, nexmax[i] - 1, premax[i], 1, p2);
for (int i = 1; i <= q; i++) que[++cntq] = question(1, sq[i].second, sq[i].first, 0, i);
sort(que + 1, que + cntq + 1, cmp2);
js(1, 1, n);
for (int i = 1; i <= cntq; i++)
if (que[i].type)
xg(1, que[i].le, que[i].ri, que[i].zh);
else
ans[que[i].zh] += cx(1, que[i].le, que[i].ri);
for (int i = 1; i <= q; i++) ans[i] += (sq[i].second - sq[i].first) * p1;
}
stack<pii> bGary;
int solve(pii x) {
while (bGary.top().first < x.first) bGary.pop();
int re = bGary.top().second;
bGary.push(x);
return re;
}
void init() {
bGary.push(make_pair(INF, 0));
for (int i = 1; i <= n; i++) premax[i] = solve(make_pair(a[i], i));
while (!bGary.empty()) bGary.pop();
bGary.push(make_pair(INF, n + 1));
for (int i = n; i >= 1; i--) nexmax[i] = solve(make_pair(a[i], i));
for (int i = 1; i <= q; i++) scanf("%d%d", &sq[i].first, &sq[i].second);
}
int main() {
scanf("%d%d%d%d", &n, &q, &p1, &p2);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
init();
solve();
for (int i = 1; i <= q; i++) printf("%lld\n", ans[i]);
return 0;
}
|