K-ое число
K-ое число
Вы работаете на компанию МакроХард в отделе структуры данных. После неудачного решения предыдущей задаче о вставки ключей, Вас попросили написать новую структуру данных, позволяющую быстро находить k-ую порядковую статистику на указанном отрезке.
Задан массив a[1...n] различных целых чисел. Необходимо отвечать на вопросы Q(i, j, k) следующего вида: "Найти k-ое число на отрезке a[i ... j], если все числа на этом отрезке предварительно отсортировать".
Например, рассмотрим отрезок a = (1, 5, 2, 6, 3, 7, 4). Рассмотрим запрос Q(2, 5, 3). Отрезком a[2 ... 5] будет (5, 2, 6, 3). Отсортировав числа, получим (2, 3, 5, 6). Третьим элементом будет 5. Ответом на запрос будет 5.
Входные данные
Первая строка содержит размер массива n и количество запросов m (1 ≤ n ≤ 100000, 1 ≤ m ≤ 5000).
Вторая строка содержит n разных целых чисел, не превосходящих 109
по абсолютному значению - массив чисел, к которому будут ставиться запросы.
Следующие m строк содержат запросы, каждый из которых состоит из трех чисел: i, j и k (0 ≤ i ≤ j ≤ n, 0 ≤ k ≤ j - i + 1) и представляет собой запрос Q(i, j, k).
Выходные данные
Для каждого запроса вывести k-ое число в отсортированном отрезке a[i ... j].
7 3 1 5 2 6 3 7 4 2 5 3 4 4 1 1 7 3
5 6 3
Şərh: This problem has huge input,so please use c-style input(scanf,printf),or you may got time limit exceed.