K-th Smallest in a Slice

Difficulty: 2200 6000 ms 128 MB

binary-search segment-tree

Answer Q queries (l, r, k): the k-th smallest element of a_l..r. The array is static.

Input: the first line has N and Q; the second line has the array; the next Q lines have l r k.

Output: one line per query.

Constraints:

• 1 ≤ N, Q ≤ 10⁵
• |values| ≤ 10⁶

Sample Tests

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

2
5

1 1
9
1 1 1

9

Read the Editorial