solution

Cho dãy số $a_1, \dots, a_n$. Với mỗi truy vấn $(l, r, k)$, hãy tìm phần tử nhỏ thứ $k$ trong đoạn con $a_l, a_{l+1}, \dots, a_r$ (nếu sắp xếp đoạn con tăng dần thì đó là phần tử ở vị trí $k$).

Sử dụng cây phân đoạn bền vững (persistent segment tree) để mỗi truy vấn chạy trong $O(\log n)$.

Ví dụ: Dãy $[3,1,2]$, truy vấn $(1,3,2)$ trả về $2$ vì đoạn con sắp xếp là $[1,2,3]$, phần tử thứ $2$ là $2$.