3437 . [模板題] Range Kth Smallest
TopCoder
Tags
Description
You are given an integer sequence $a_ 0, a_ 1, ..., a_ {N-1}$ with the length $N$.
Process the following $Q$ queries in order:
l_i r_i k_i: Print $k_ i+1$ th smallest value in $(a_ {l_ i}, a_ {l_ i + 1}, ..., a_ {r_ i - 1})$.
Input Format
$N$ $Q$
$a_ 0$ $a_ 1$ ... $a_ {N - 1}$
$l_ 0$ $r_ 0$ $k_ 0$
$l_ 1$ $r_ 1$ $k_ 1$
:
$l_ {Q-1}$ $r_ {Q-1}$ $k_ {Q-1}$
Output Format
Sample Input 1
5 3 1 4 0 1 3 0 5 2 1 3 1 3 4 0
Sample Output 1
1 4 1
Hints
- $1 \leq N \leq 2 \times 10^ {5}$
- $1 \leq Q \leq 2 \times 10^ {5}$
- $0 \leq a_ i \leq 10^ {9}$
- $0 \leq l_ i < r_ i \leq N$
- $0 \leq k_ i < r_ i - l_ i$
Problem Source
Subtasks
| No. | Testdata Range | Score |
|---|