# 2. 题解

$R[i]$表示在位置 $i$右边的第一个比 $K[i]$大的数字的位置

1. 点对 $(L[i], R[i])$可以提供 $P1$的战斗力（显然符合第一种条件）
2. 点对 $(i, i + 1)$可以提供 $P1$的战斗力（题目描述有讲）
3. 点对（们）$(L[i], i + 1 \sim R[i] – 1)$可以提供 $P2$的战斗力（$K[L[i]] > K[i] > K[i + 1 \sim R[i] – 1]$）
4. 点对（们）$(L[i] + 1 \sim i – 1, R[i])$可以提供 $P2$的战斗力（$K[L[i] + 1 \sim i – 1] < K[i] < K[R[i]]$）

$(1\sim 5, 8)$（点对定点为右端点，右端点为 $8$，左端点 $\in [1,5]$）

/*
* 影魔.cpp
* This file is part of 影魔
*
* Copyright (C) 2018 - xzy
*
* 影魔 is free software; you can redistribute it and/or modify
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* 影魔 is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
* GNU General Public License for more detops.
*
* You should have received a copy of the GNU General Public License
* along with 影魔. If not, see <http://www.gnu.org/licenses/>.
*/

#pragma GCC optimize("Ofast")
#pragma GCC target("sse3","sse2","sse")
#pragma GCC target("avx","sse4","sse4.1","sse4.2","ssse3")
#pragma GCC target("f16c")
#pragma GCC optimize("inline","fast-math","unroll-loops","no-stack-protector")
#pragma GCC diagnostic error "-fwhole-program"
#pragma GCC diagnostic error "-fcse-skip-blocks"
#pragma GCC diagnostic error "-funsafe-loop-optimizations"
#pragma GCC diagnostic error "-std=c++14"

#include <bits/stdc++.h>

#define NS (200005)
#define PS (11400005)

using namespace std;

typedef long long LL;

template<typename _Tp> inline void IN(_Tp& dig)
{
char c; bool flag = 0; dig = 0;
while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
if (flag) dig = -dig;
}

struct TII{int x, y, z;};

struct N {LL d, tag; int l, r;} e[PS];

int size;

struct CMT
{
#define LEN (min(R, r) - max(L, l) + 1)
int root[NS];
void update(int l, int r, LL d, int L, int R, int& x, int y)
{
x = ++size, e[x] = e[y], e[x].d += LEN * d;
if (l <= L && R <= r) {e[x].tag += d; return;}
int Mid = (L + R) >> 1;
if (l <= Mid) update(l, r, d, L, Mid, e[x].l, e[y].l);
if (r > Mid) update(l, r, d, Mid + 1, R, e[x].r, e[y].r);
}
LL query(int l, int r, int L, int R, int a)
{
if (!a) return 0;
if (l <= L && R <= r) return e[a].d;
int Mid = (L + R) >> 1; LL res = e[a].tag * LEN;
if (l <= Mid) res += query(l, r, L, Mid, e[a].l);
if (r > Mid) res += query(l, r, Mid + 1, R, e[a].r);
return res;
}
#undef LEN
}tl, tr;

int n, m, p1, p2, k[NS], lt[NS], rt[NS];

int top, que[NS], qid[NS];

vector<TII> ch1[NS], ch2[NS];

void Init()
{
top = 1;
for (int i = 1; i <= n; i += 1) rt[i] = n + 1;
for (int i = 1; i <= n; i += 1)
{
while (1 < top && que[top - 1] < k[i])
rt[qid[top - 1]] = i, top--;
lt[i] = qid[top - 1], qid[top] = i, que[top++] = k[i];
}
for (int i = 1; i <= n; i += 1)
{
if (lt[i] && rt[i] <= n)
ch1[lt[i]].push_back((TII){rt[i], rt[i], p1});
if (lt[i] && i + 1 <= rt[i] - 1)
ch1[lt[i]].push_back((TII){i + 1, rt[i] - 1, p2});
if (rt[i] <= n && lt[i] + 1 <= i - 1)
ch2[rt[i]].push_back((TII){lt[i] + 1, i - 1, p2});
}
}

void Build()
{
for (int i = 1; i <= n; i += 1)
{
tl.root[i] = tl.root[i - 1];
for (vector<TII>::iterator j = ch1[i].begin(); j != ch1[i].end(); j++)
tl.update(j->x, j->y, j->z, 1, n, tl.root[i], tl.root[i]);
tr.root[i] = tr.root[i - 1];
for (vector<TII>::iterator j = ch2[i].begin(); j != ch2[i].end(); j++)
tr.update(j->x, j->y, j->z, 1, n, tr.root[i], tr.root[i]);
}
}

int main(int argc, char const* argv[])
{
IN(n), IN(m), IN(p1), IN(p2);
for (int i = 1; i <= n; i += 1) IN(k[i]);
Init(), Build();
while (m--)
{
int a, b; LL ans = 0;
IN(a), IN(b);
ans += tl.query(a, b, 1, n, tl.root[b]);
ans -= tl.query(a, b, 1, n, tl.root[a - 1]);
ans += tr.query(a, b, 1, n, tr.root[b]);
ans -= tr.query(a, b, 1, n, tr.root[a - 1]);
ans += 1ll * p1 * (b - a);
printf("%lld\n", ans);
}
return 0;
}