P3722 [AHOI2017/HNOI2017] Shadow Fiend

Shadow Fiend, Nevermore, is said to have the soul of a poet. In fact, the poet souls he has devoured already number in the tens of thousands. For hundreds of years, he has collected all kinds of souls, including poets, priests, emperors, beggars, slaves, sinners, and of course, heroes. Each soul has its own combat power, and Shadow Fiend increases his attack power by relying on these combat powers.

Nevermore has $n$ souls. Inside the vast body of the Shadow Fiend, they can line up in a row, labeled from left to right $1$ to $n$. The $i$-th soul has combat power $k_i$, and souls provide attack power for the Shadow Fiend in the form of pairs. For a soul pair $i, j$ with $i < j$, if there is no $k_s$ with $i < s < j$ that is greater than $k_i$ or greater than $k_j$, then it provides $p_1$ attack power. In another case, let $c$ be the maximum of $k_{i + 1}, k_{i + 2}, \cdots, k_{j - 1}$. If $c$ satisfies $k_i < c < k_j$, or $k_j < c < k_i$, then it provides $p_2$ attack power. When such a $c$ does not exist, it naturally does not provide this $p_2$ attack power. In all other cases, the pair does not provide any attack power. Shadow Fiend’s close friend Lifestealer visited him one day and was captivated by these souls. He wants to know, for any interval $[a, b]$, how much attack power is provided by the soul pairs within these intervals, that is, consider the sum of the attack power provided by all soul pairs $i, j$ satisfying $a \le i < j \le b$. Incidentally, the souls’ combat powers form a permutation of $1$ to $n$: $k_1, k_2, \cdots, k_n$.

The first line contains four integers $n, m, p_1, p_2$. The second line contains $n$ integers $k_1, k_2, \cdots, k_n$. Then there are $m$ lines. Each line contains two integers $a, b$, representing a query asking how much attack power is provided by the soul pairs within the interval $[a, b]$.

Output $m$ lines, each containing one answer, corresponding to the $m$ queries in order.

For $30\%$ of the testdata, $1 \le n, m \le 500$. For another $30\%$ of the testdata, $p_1 = 2 p_2$. For $100\%$ of the testdata, $1 \le n, m \le 200000$, $1 \le p_1, p_2 \le 1000$. Translated by ChatGPT 5