Hossam and Range Minimum Query
Contest: Codeforces Round 837 (Div. 2)
Difficulty rating: 2500
Tags: binary search, bitmasks, data structures, hashing, probabilities, strings, trees

Hossam gives you a sequence of integers $$$a_1, \, a_2, \, \dots, \, a_n$$$ of length $$$n$$$. Moreover, he will give you $$$q$$$ queries of type $$$(l, \, r)$$$. For each query, consider the elements $$$a_l, \, a_{l + 1}, \, \dots, \, a_r$$$. Hossam wants to know the smallest number in this sequence, such that it occurs in this sequence an odd number of times.

You need to compute the answer for each query before process the next query.

Input format:
The first line of the input contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$), the length of the sequence.

The second line contains $$$n$$$ integers $$$a_1, \, a_2, \, \dots, \, a_n$$$ ($$$1 \le a_i \le 10^9$$$).

The third line contains one integer $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$), the number of queries.

Each of the next $$$q$$$ lines contains two integers $$$a$$$ and $$$b$$$ ($$$0 \le a, \, b \le 2 \cdot 10^9$$$), the numbers used to encode the queries.

Let $$$\mathrm{ans}_i$$$ be the answer on the $$$i$$$-th query, and $$$\mathrm{ans}_0$$$ be zero. Then $$$$$$l_i = a_i \oplus \mathrm{ans}_{i - 1},$$$$$$ $$$$$$r_i = b_i \oplus \mathrm{ans}_{i - 1},$$$$$$ where $$$l_i, \, r_i$$$ are parameters of the $$$i$$$-th query and $$$\oplus$$$ means the bitwise exclusive or operation. It is guaranteed that $$$1 \le l \le r \le n$$$.

Output format:
For each query, print the smallest number that occurs an odd number of times on the given segment of the sequence.

If there is no such number, print $$$0$$$.

Constraints:
Time limit: 1.5 s
Memory limit: 256.0 MB

Note:
In the example,

$$$$$$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.$$$$$$

Example input:
5
1 2 1 2 2
6
1 2
0 2
0 6
0 5
2 2
3 7

Example output:
1
2
1
0
2
2

Example input:
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

Example output:
51
55
19
48
76
19
23
19
55
19

Editorial:
Note that we were asked to solve the problem in online mode. If this were not the case, then the Mo Algorithm could be used.
How to solve this task in online mode? Consider two ways.
The first way is as follows. Let's build a persistent bitwise trie $$$T$$$ on a given array, where the $$$i$$$-th version of the trie will store numbers $$$x$$$ such that $$$x$$$ occurs on the subsegment $$$a[1\dots i]$$$ an odd number of times.
This can be done as follows. Let $$$T_0$$$ be an empty trie, and $$$T_i$$$ will be obtained as follows: first we assign $$$T_i = T_{i - 1}$$$; then, if $$$a_i$$$ occurs in $$$T_{i - 1}$$$, then we will erase the number $$$a_i$$$ from $$$T_i$$$, otherwise we will insert it there.
Suppose we need to get answer on the query $$$[l, \, r]$$$. Note that if $$$x$$$ is included in $$$T_r$$$, but is not included in $$$T_{l - 1}$$$ (or is included in $$$T_{l - 1}$$$, but is not included in $$$T_r$$$), then this means that the number $$$x$$$ on the segment $$$a[l\dots r]$$$ occurs an odd number of times. Otherwise, the number $$$x$$$ occurs an even number of times (recall that $$$0$$$ is an even number). Thus, we need to find a minimum number $$$x$$$ such that it occurs either in $$$T_{l - 1}$$$ or in $$$T_r$$$, but not in both at once. If there is no such number, then you need to output $$$0$$$.
Let's go down $$$T_{l - 1}$$$ and $$$T_r$$$ in parallel on the same prefix of the number. If $$$T_{l - 1}$$$ and $$$T_r$$$ are equal, then the same numbers are contained there, and then the answer is $$$0$$$. Next, we will assume that the answer is not $$$0$$$. The left subtree of the vertex is the son to whom the transition along the edge of $$$0$$$ is going, and the right subtree is the vertex to which the transition along the edge of $$$1$$$ is going. Let us now stand at the vertices $$$v$$$ and $$$u$$$, respectively. If the left subtrees of $$$v$$$ and $$$u$$$ are equal, it means that the same numbers are contained there, so there is no point in going there, so we go along the right edge. Otherwise, the left subtree of $$$v$$$ contains at least one number that is not in the left subtree of $$$u$$$ (or vice versa), so we will go down the left edge. The number in which we ended up will be the answer.
Note that in order to compare two subtrees for equality, you need to use the hashing technique of root trees. Then we can compare the two subtree for $$$\mathcal{O}(1)$$$.
Thus, we get the asymptotics $$$\mathcal{O((n+q)\log{max(a)})}$$$. If we compress the numbers of the sequence $$$a$$$ in advance, then we can get the asymptotics of $$$\mathcal{O((n + q) \log{n})}$$$.
Let's consider the second way. Let's compress the numbers in the sequence $$$a$$$ in advance. Let $$$pref_{ij} = 0$$$ if the prefix $$$i$$$ contains the number $$$a_j$$$ an even number of times, and $$$pref_{ij} = 1$$$ if the prefix $$$i$$$ contains the number $$$a_j$$$ an odd number of times.
Then, in order to get an answer to the query $$$[l\dots r]$$$, we need to take the "bitwise exclusive OR" arrays $$$pref_{l - 1}$$$ and $$$pref_r$$$ and find in it the minimum $$$j$$$ such that $$$pref_{ij} = 1$$$. The number $$$j$$$ will be the answer.
Obviously, now this solution need much time and memory.
In order to optimize the amount of memory consumed, we will use bitsets. However, even in this case, we consume memory of the order of $$$\mathcal{o}(h^2 \, / \, 64)$$$, which is still a lot. So let's not remember about all $$$pref_i$$$, but only some. For example, let's get some constant $$$k$$$ and remeber only about $$$pref_0, \, pref_k, \, pref_{2k}, \, \data\, pref_{pk}$$$.
Then, when we need to answer the next query $$$[l \dots r]$$$, we will find the right block on which we store almost all the numbers we are looking for, and then we will insert/erase for $$$\mathcal{O(k)}$$$ missing numbers.
If you select $$$k \sim\sqrt{n}$$$, then this solution will fit in memory. However, if you use std::bitset<> in C++, then most likely this solution will still receive the verdict Time Limit. Therefore, to solve this problem, you need to write your own fast bitset.
The asymptotics of such a solution would be $$$\mathcal{O}(n\, (n+q) \, / \, 64)$$$. However, due to a well-chosen $$$k$$$ and a self-written bitset, the constant in this solution will be very small and under given constraints, such a solution can work even faster than the first one.