Xor of unique values on segment

Revision en1, by prudent, 2018-06-26 23:50:20

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

Tags xor, data structures, range query, uniqueness

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English prudent 2018-06-26 23:50:20 702 Initial revision (published)