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

*x*

_{1},

*x*

_{2},

*x*

_{3}, ...,

*x*

_{k}is set of unique values from

*a*

_{l},

*a*

_{l + 1},

*a*

_{l + 2}, ...,

*a*

_{r - 2},

*a*

_{r - 1},

*a*

_{r}, then output

*x*_{1}xor*x*_{2}xor*x*_{3}xor ... xor*x*_{k}1 ≤ *n*, *q* ≤ 10^{6}

for all *i*, 1 ≤ *a*_{i} ≤ 10^{9}

**TL: 3.5 secondsML: 256 megabytes**

How to solve it?

If it's possible, I'd like a solution which uses some of data structures listed below:**Segment TreeBinary Rise/LiftTrieMerge Sort Tree**

I think, it can be solved with MO`s algorithm and hashset.

Or without hashset using coordinates compression.

I think you can avoid hashes / set by applying coordinate compression on the array, while maintaining original values to be able to also compute the xor. This way, you can just keep an array of size

Nto keep frequency of each value.This will have time complexity of which I'm not completely sure may pass as

N≤ 10^{6}usually requiresO(NlogN) solution, but you should try it anyway as 3.5s is larger than usual time limits :)you can use ofline segment tree for optimize solution.

Can You please further explain how can I apply it?

This is 703D - Mishka and Interesting sum. Sqrt-decomposition solutions generally don't pass in this problem, unless you use fast I/O and coordinate compression.

I assume what you mean is that given a range [

l,r], the answer is as if we insert all these elements into a set, and then compute the xor of all values in the set.Construct an array

BfromA:B_{i}=j, such thatjis the last index inAin which we've seen the valueA_{i}, or -1 otherwise. (Formally, suchjthatA_{j}=A_{i},A_{k}≠A_{i}, forj<k<i, or -1 if no suchjexists). You can construct this in .Now the task becomes "Given a range [

l,r], compute the xor of allA_{i}for whichB_{i}<l". This can be solved with a merge sort tree in (make the tree of pairs (B_{i},A_{i}), keep it sorted byB_{i}, and then each query requires binary searches on nodes in the tree, while after each binary search you need to compute the prefix xor ofA_{i}in a specific node, so you can preprocess prefix xors for all nodes in the tree).You can also solve it in using a wavelet tree.

Doesn't such

jalways exist, sincej≥iandA_{j}=A_{i}?No, read more carefully. Noam defined it with

j<i.Does he mean last

j<i, thatA_{j}=A_{i}?He meant last

jbeforei. Look at the mathematical definition in the bracket.WOW, great solution, I'll definitely implement it!

Thank You very much!

I implemented it, but I'm getting TLE which I shouldn't get because my solution uses

O(NlogN) memory, right? Can You please view my submission 39701020?You can use segment tree by sorting the queries in increasing R, the idea is same as Noam527 said.

Don't You know why I get TLE?

If You know/can know by viewing my code, please say me where's my mistake.