题意：https://loj.ac/problem/2019
solution1：
首先要看清楚题意，两种情况不是互补的。
(1:forall sin[i+1,j-1],A_s<Ai,A_s<A_j)时产生(p_1)的贡献
(2:A_i<max{A[i+1...j-1]}<A_j)或者(A_j<max{A[i+1...j-1]}<A_i)时产生(p_2)的贡献
(3:A_i<max{A[i+1...j-1]},A_j<max{A[i+1...j-1]})不产生贡献
(4:A_i)形成排列，不存在相等关系。
每个产生贡献的点对((i,j))依赖(max_{k=i+1}^{j-1}A_k)，因此考虑算每个(A_k)的贡献。
考虑固定每个(A_i)为最大值，设在(i)之前离(i)最近的大于(A_i)的为(A_j)，(i)之后离(i)最近的大于(A_i)的为(A_k)
注意，考虑前后相邻的大于(A_i)的点的原因是如果左右端点越过(j)或者(k)，明显(A_i)不再会作为最大值
因此不应该越界，又由前面的整理，可以得到(A[j+1...i-1]<A_i),(A[i+1...k-1]<A_i)
产生(p_1)贡献的点对：有且仅有((j,k))。
产生(p_2)贡献的点对：固定(j)为左端点，且右端点在([i+1,k-1])内；固定(k)为右端点，且左端点在([j+1,i-1])内
然后考虑怎么维护。
首先可以把询问拆成两个前缀相减，然后把贡献和询问都离线掉
扫到一个询问先把pos(leq)当前询问位置的贡献加上，然后根据是询问的左端点还是右端点维护答案。
这样对于一个询问来说如果贡献越界，那么就会出现在两次询问里消掉
#include<cstdio>
#include<cstring>
#define R register
#include<algorithm>
const int N = 2e5+7;
typedef long long LL;
#define debug printf("GG
")
LL ans[N], A[N];
struct QS {
int x, id;
} q[N*2];
struct Point {
int pos, l, r, w;
} p[N*2];
int st[N], top, tot, vis[N];
struct BIT {
LL c[N*2][2];int n;
#define lbt(x) (x & (-x))
inline void update(int x, int type, LL k) {
while (x <= n) c[x][type] += k, x += lbt(x);
}
inline LL ask(int x, int type) {
LL res = 0;
while (x) res += c[x][type], x -= lbt(x);
return res;
}
inline void Modify(int l, int r, int w) {
update(l, 0, 1LL * w), update(r + 1, 0, (LL)-w),
update(l, 1, 1LL * l * w), update(r + 1, 1, 1LL * (r + 1) * -w);
}
inline LL query(int l, int r) {
return (LL)(((LL)r + 1LL) * ask(r, 0) - ask(r, 1))
- (LL)((LL)l * ask(l - 1, 0) - ask(l - 1, 1));
}
}t;
inline int cmp1(QS a, QS b) {
return a.x < b.x;
}
inline int cmp2(Point a, Point b) {
return a.pos < b.pos;
}
int n, m, p1, p2, nxt[N], pre[N], L[N], RR[N];
void findpn() {
for (R int i = 1; i <= n; i++) {
while (top && A[st[top]] < A[i]) nxt[st[top--]] = i;
pre[i] = st[top], st[++top] = i;
}
for (R int i = 1; i <= n; i++)
if (!nxt[i]) nxt[i] = n + 1;
for (R int i = 1; i <= n; i++) {
int pr = pre[i], nx = nxt[i];
if (pr > 0 && nx <= n) p[++tot] = (Point){pr, nx, nx, p1};
if (pr > 0 && i + 1 <= nx - 1) p[++tot] = (Point){pr, i + 1, nx - 1, p2};
if (nx <= n && i - 1 >= pr + 1) p[++tot] = (Point){nx, pr + 1, i - 1, p2};
}
//debug;
std :: sort(p + 1, p + tot + 1, cmp2);
}
int main() {
scanf("%d%d%d%d", &n, &m, &p1, &p2);
t.n = n;
for (R int i = 1; i <= n; i++)
scanf("%d", &A[i]);
for (R int i = 1; i <= m; i++) {
scanf("%d%d", &L[i], &RR[i]);
if (L[i] == RR[i]) continue;
q[(i - 1) * 2 + 1] = (QS){L[i] - 1, i}, q[i * 2] = (QS){RR[i], i};
}
std :: sort(q + 1, q + m * 2 + 1, cmp1);
findpn();
int pos = 1, cnt = 1, up = 2 * m;
for (R int i = 1; i <= up; i++) {
while (cnt <= q[i].x)
t.Modify(cnt + 1, cnt + 1, (LL)p1), cnt++;
while (pos <= tot && p[pos].pos <= q[i].x)
t.Modify(p[pos].l, p[pos].r, (LL)p[pos].w), pos++;
if (!vis[q[i].id])
ans[q[i].id] = -t.query(L[q[i].id], RR[q[i].id]), vis[q[i].id] = 1;
else ans[q[i].id] += t.query(L[q[i].id], RR[q[i].id]);
}
for (R int i = 1; i <= m; i++)
printf("%lld
", ans[i]);
return 0;
}