K-th nhỏ nhất trong đoạn

Buổi 30 — Persistent Segment Tree
Points
12
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Submissions
Đề bài

Cho dãy $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$ của đoạn $a_l,\dots,a_r$ (tính cả trùng lặp).

Dữ liệu vào

Dòng đầu: $n,q$. Dòng hai: $n$ số nguyên. Tiếp theo $q$ dòng, mỗi dòng gồm $l, r, k$ với $1\le k\le r-l+1$.

Dữ liệu ra

Với mỗi truy vấn in một dòng là giá trị tìm được.

Ví dụ

Input

5 5
-8 3 10 7 -1
2 2 1
1 1 1
5 5 1
1 4 1
5 5 1

Output

3
-8
-1
-8
-1
Giới hạn
  • $1\le n,q\le 10^5$; $|a_i|\le 10^9$.
  • Thời gian: 2 giây; bộ nhớ: 256 MB.
Draft saved