Pairs' value - MarisaOJ: Marisa Online Judge

Pairs' value

Time limit: 1000 ms
Memory limit: 256 MB
Given a permutation $a$ consisting of integers from $1$ to $n$. For a pair of indices $i < j$, with $c = \text{max}(a_{i+1}, a_{i+2}, \ldots, a_{j-1})$, the value of this pair is defined as: - $x$ if $c \leq \text{min}(a_i, a_j)$ or $i = j - 1$. - $y$ if $a_i < c < a_j$ or $a_i > c > a_j$. - $0$ in all other cases. Given $q$ queries $l, r$, calculate the total value of all pairs $(a, b)$ such that $l \leq a < b \leq r$. ### Input - The first line contains four integers $n, q, x, y$. - The second line contains $n$ integers representing the permutation $a$. - The next $q$ lines each contain two integers $l, r$ representing a query. ### Output - For each query, print the total value of all pairs that satisfy the condition. ### Constraints - $1 \leq n, q \leq 2 \times 10^5$. - $1 \leq x, y \leq 1000$. ### Example Input: ``` 10 5 2 3 9 3 5 4 10 7 6 8 1 2 1 7 1 5 1 9 5 9 1 3 ``` Output: ``` 27 20 38 18 6 ``` ### Subtasks - Subtask 1 (30% of the points): $1 \leq n, q \leq 500$. - Subtask 2 (30% of the points): $x = 2 \times y$. - Subtask 3 (40% of the points): No additional constraints.