K-query - MarisaOJ: Marisa Online Judge

You are given array

A

$A$ of

n

$n$ integers. There are

q

$q$ queries, each of the form

(l, r, k)

$(l, r, k)$ , count the number of numbers larger than

k

$k$ in the subarray

A_{l}, A_{l + 1}, . . ., A_{r}

$A_l,A_{l + 1},...,A_r$ . ### Input - The first line contains 2 integers

n, q

$n, q$ . - The second line contains

n

$n$ integers

A_{i}

$A_i$ . - The next

q

$q$ lines, each line contains 3 integers

l, r, k

$l, r,k$ , a query. ### Output - Print

q

$q$ integers, the answers to

q

$q$ queries. ### Constraints -

1 \leq n, q \leq 10^{5}

$1 \le n, q\le 10^5$ . -

1 \leq A_{i}, k \leq 10^{9}

$1 \le A_i, k \le 10^9$ . ### Example Input:

5312232131152345

$5 3 1 2 2 3 2 1 3 1 1 5 2 3 4 5$

Output:

210

$2 1 0$

Topic

Data structure

Rating

1500

Solution (0)

Solution