#22. Kichik k-element (Order Statistics)
Sizga n ta butun sondan iborat A massiv va q ta so'rov beriladi. Har bir so'rovda sizga uchta son — l, r va k taqdim etiladi. Sizning vazifangiz massivning faqatgina l-indeksdan r-indeksgacha bo'lgan qismini ajratib olib, uni o'sish tartibida saralagandan so'ng, shu qismdagi k-o'rinda turgan sonni (ya'ni k-chi eng kichik elementni) topishdir.
Birinchi qatorda n va q sonlari beriladi. Ikkinchi qatorda n ta elementdan iborat massiv kiritiladi. Keyingi q ta qatorda l, r va k sonlari beriladi.
Har bir so'rov uchun so'ralgan k-chi eng kichik elementni alohida qatorda chiqaring.
1 ≤ n, q ≤ 2×10⁵
You are given an array A of n integers and q queries. In each query, you are given three numbers — l, r, and k. Your task is to extract the subarray from the l-th to the r-th index, sort it in ascending order, and find the k-th number in this sorted subarray (i.e., the k-th smallest element).
The first line contains the numbers n and q. The second line contains an array of n elements. The next q lines contain the numbers l, r, and k.
For each query, output the requested k-th smallest element on a new line.
1 ≤ n, q ≤ 2×10⁵
Вам дан массив A из n целых чисел и q запросов. В каждом запросе вам даются три числа — l, r и k. Ваша задача — выделить подмассив от l-го до r-го индекса, отсортировать его по возрастанию и найти k-е число в этом отсортированном подмассиве (то есть k-й по величине минимальный элемент).
В первой строке заданы числа n и q. Во второй строке задан массив из n элементов. В следующих q строках заданы числа l, r и k.
Для каждого запроса выведите искомое k-е минимальное число в отдельной строке.
1 ≤ n, q ≤ 2×10⁵
Sizga n ta butun sondan iborat A massiv va q ta so'rov beriladi. Har bir so'rovda sizga uchta son — l, r va k taqdim etiladi. Sizning vazifangiz massivning faqatgina l-indeksdan r-indeksgacha bo'lgan qismini ajratib olib, uni o'sish tartibida saralagandan so'ng, shu qismdagi k-o'rinda turgan sonni (ya'ni k-chi eng kichik elementni) topishdir.
Kiruvchi ma'lumotlar
Birinchi qatorda n va q sonlari beriladi. Ikkinchi qatorda n ta elementdan iborat massiv kiritiladi. Keyingi q ta qatorda l, r va k sonlari beriladi.
Chiquvchi ma'lumotlar
Har bir so'rov uchun so'ralgan k-chi eng kichik elementni alohida qatorda chiqaring.
Cheklovlar
1 ≤ n, q ≤ 2×10⁵
Misollar
5 2 5 4 3 2 1 1 5 1 1 5 5
1 5