P3834 [Template] Persistent Segment Tree 2

This is a very classic introductory problem on the persistent value segment tree (权值线段树) — the static range $ k $-th smallest query.

As stated, given a sequence $ a $ of $ n $ integers, for each specified closed interval $ [l, r] $, query the $ k $-th smallest value within the interval.

The first line contains two integers, the length $ n $ of the sequence and the number $ m $ of queries. The second line contains $ n $ integers; the $ i $-th integer is the $ i $-th element $ a_i $ of the sequence. Each of the next $ m $ lines contains three integers $ l, r, k $, denoting the $ k $-th smallest value within the range $ [l, r] $.

For each query, output one line with a single integer, the answer.

### Sample 1 Explanation $n=5$, the sequence length is $5$, and the sequence from the first term is $\{25957, 6405, 15770, 26287, 26465\}$. - The first query asks for the first smallest value in $[2, 2]$, which is $6405$. - The second query asks for the first smallest value in $[3, 4]$, which is $15770$. - The third query asks for the first smallest value in $[4, 5]$, which is $26287$. - The fourth query asks for the second smallest value in $[1, 2]$, which is $25957$. - The fifth query asks for the first smallest value in $[4, 4]$, which is $26287$. ### Constraints - For $10\%$ of the testdata, $1 \leq n,m \leq 10$. - For $25\%$ of the testdata, $1 \leq n,m \leq 10^3$. - For $40\%$ of the testdata, $1 \leq n,m \leq 10^5$. - For $50\%$ of the testdata, $1 \leq n,m \leq 2\times 10^5$, $0\le a_i \leq 2\times 10^5$. - For all testdata, $1 \leq n,m \leq 2\times 10^5$, $0\le a_i \leq 10^9$, $1 \leq l \leq r \leq n$, $1 \leq k \leq r - l + 1$. Translated by ChatGPT 5