Given an array of n positive integers called a
For each of q queries which are described with integers 1 ≤ l ≤ r ≤ n, output xor of unique values in segment(l, r), i.e. if x1, x2, x3, ..., xk is set of unique values from al, al + 1, al + 2, ..., ar - 2, ar - 1, ar, then output x1 xor x2 xor x3 xor ... xor xk
1 ≤ n, q ≤ 106
for all i, 1 ≤ ai ≤ 109
TL: 3.5 seconds
ML: 256 megabytes
How to solve it?
If it's possible, I'd like a solution which uses some of data structures listed below:
Segment Tree
Binary Rise/Lift
Trie
Merge Sort Tree