Голосование в айыл окмоту
В айыл окмоту 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 элементов.
Комментарии