e-olymp
favorite Нам необходимо немного Вашей помощи чтобы сайт продолжал работать, нажмите на банер чтобы узнать больше.
Соревнования

ADA University - March 7 - Segment Tree

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 (1n100000, 1m5000).

Вторая строка содержит n разных целых чисел, не превосходящих 109 по абсолютному значению - массив чисел, к которому будут ставиться запросы.

Следующие m строк содержат запросы, каждый из которых состоит из трех чисел: i, j и k (0ijn, 0kj - i + 1) и представляет собой запрос Q(i, j, k).

Выходные данные

Для каждого запроса вывести k-ое число в отсортированном отрезке a[i ... j].

Лимит времени 1 секунда
Лимит использования памяти 128 MiB
Входные данные #1
7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3
Выходные данные #1
5
6
3

Объяснение: Большой объем входных данных, используйте c-стиль чтения данных (scanf,printf), иначе будет Тайм Лимит

Источник 2004 NEERC, Northern Subregion, October 30, Problem K