Codeforces Round 837 (Div. 2) |
---|
Закончено |
Хоссам дал вам последовательность целых чисел $$$a_1, \, a_2, \, \dots, \, a_n$$$ длины $$$n$$$. Кроме того, он последовательно дает вам $$$q$$$ запросов вида $$$(l, \, r)$$$. Для каждого запроса он хочет знать среди чисел $$$a_l, \, a_{l + 1}, \, \dots, \, a_r$$$ такое минимальное число, что оно встречается в заданном отрезке последовательности нечетное количество раз.
Вы должны посчитать ответ на каждый запрос, прежде чем отвечать на следующий.
В первой строке входных данных задано единственное целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — длина последовательности.
Во второй строке входных данных задана последовательность из $$$n$$$ целых чисел $$$a_1, \, a_2, \, \dots, \, a_n$$$ ($$$1 \le a_i \le 10^9$$$).
В третьей строке задано целое число $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — количество запросов.
Затем следуют $$$q$$$ строк, в каждой из которой задано два целых числа $$$a$$$ и $$$b$$$ ($$$0 \le a, \, b \le 2 \cdot 10^9$$$) — числа, с помощью которых кодируются границы запроса.
Пусть $$$\mathrm{ans}_i$$$ ответ на $$$i$$$-й запрос, и $$$\mathrm{ans}_0$$$ равен нулю. Тогда $$$$$$l_i = a_i \oplus \mathrm{ans}_{i - 1},$$$$$$ $$$$$$r_i = b_i \oplus \mathrm{ans}_{i - 1},$$$$$$ где $$$l_i, \, r_i$$$ параметры $$$i$$$-го запроса и $$$\oplus$$$ означает битовое исключающие или. Гарантируется, что $$$1 \le l \le r \le n$$$.
Для каждого запроса выведите минимальное число, которое встречается на заданном отрезке последовательности нечетное количество раз.
Если такого числа не существует, выведите $$$0$$$.
5 1 2 1 2 2 6 1 2 0 2 0 6 0 5 2 2 3 7
1 2 1 0 2 2
10 51 43 69 48 23 52 48 76 19 55 10 1 1 57 57 54 62 20 27 56 56 79 69 16 21 18 30 25 25 62 61
51 55 19 48 76 19 23 19 55 19
В данном примере
$$$$$$l_1 = 1, \, r_1 = 2,$$$$$$ $$$$$$l_2 = 1, \, r_2 = 3,$$$$$$ $$$$$$l_3 = 2, \, r_3 = 4,$$$$$$ $$$$$$l_4 = 1, \, r_4 = 4,$$$$$$ $$$$$$l_5 = 2, \, r_5 = 2,$$$$$$ $$$$$$l_6 = 1, \, r_6 = 5.$$$$$$
Название |
---|