Pairs' value - MarisaOJ: Marisa Online Judge

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.

Topic

Data structure

Rating

2000

Solution (0)

Solution