Голосование в айыл окмоту


Отправить решение Решать в редакторе

Сложность: 85%
Очки: 100 (частичный балл)
Ограничение по времени: 3.0s
Ограничение по памяти: 256M

Автор:
Типы задач
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

В айыл окмоту n депутатов сидят в ряд, депутат i оценил проект бюджета числом a[i]. Председатель задаёт вопросы: «если взять депутатов с l по r и упорядочить их оценки по возрастанию, какая оценка окажется k-й?»

Председатель хитрый: каждый следующий вопрос зависит от ответа на предыдущий, поэтому отвечать нужно сразу, по одному.

Рисунок

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

В первой строке — числа n и q (1 ≤ n, q ≤ 2 · 10⁵). Во второй строке — n чисел a[i] (0 ≤ a[i] ≤ 10⁹). В каждой из следующих q строк — три числа x y z. Пусть last — ответ на предыдущий вопрос (для первого вопроса last = 0). Настоящий вопрос получается так: l = ((x xor last) mod n) + 1, r = ((y xor last) mod n) + 1; если l > r, их меняют местами; k = ((z xor last) mod (r − l + 1)) + 1.

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

Для каждого вопроса выведите ответ в отдельной строке.

Пример 1

Вход:

5 2
5 1 4 2 3
0 4 2
3 5 1

Выход:

3
1

Пояснение

Первый вопрос: last = 0, l = 1, r = 5, k = 3 — третья по величине из оценок 5 1 4 2 3 равна 3. Второй вопрос: last = 3, l = ((3 xor 3) mod 5) + 1 = 1, r = ((5 xor 3) mod 5) + 1 = 2, k = ((1 xor 3) mod 2) + 1 = 1, ответ 1.

Система оценивания

Решение проверяется на 20 тестах, каждый стоит 5 баллов. В 20 % тестов n, q ≤ 1000.

Подсказка

Персистентное дерево отрезков: версия i хранит количества значений среди первых i элементов.


Комментарии

Еще нет ни одного комментария.