e-olymp
Məsələlər

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

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

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

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

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

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3
Çıxış verilənləri #1
5
6
3

Şərh: This problem has huge input,so please use c-style input(scanf,printf),or you may got time limit exceed.

Mənbə 2004 NEERC, Northern Subregion, October 30, Problem K