That's how I solved it and it seems similar to arsijo's solution. Yes, there is some more complicated, fully deterministic solution, but I couldn't understand it in the few minutes I've talked to the author. The official solution had complexity O(N^1.5) with no extra log (even though, the hashing solution works in the same asymptotically time if you consider mapping to be O(1) as I usually do)

Ok I think I get it now.

Assign a random large value to each possible value in the range [1..1000000].

We'll determine that an interval [l..r] is good if the xor of all a_j for all l ≤ j ≤ r which satisfies the condition that there exist an index k with l ≤ k < j so that a_k = a_j is 0. We call this xor value F(l, r) for convenience.

For each position i, let nxt[i] denote the next position with the same value as a_i (if it does not exist, set is as ∞).

We can do a simple O(n) loop to compute F(1, i) for all i, and store them in some array, say f[i].

For each position l, we'll calculate the number of indices r such that F(l, r) = 0 quickly. To do so, we need to be able to update the values of f[i] after solving the problem for position l and also query the number of f[i] with i ≥ l and f[i] = 0 fast.

Note that after we finish processing position l, updating the values of f[i] is just xor-ing all values of f[k] with k ≥ nxt[l] by V[a[l]], where V[a[l]] is the hash value assigned to a[l].

Thus, we basically have to xor a suffix with a certain value v and find the number of 0s in a suffix. This can be easily done with sqrt decomposition on the array if we store a map of values of each block and also another value shift[i] for each block denoting that the whole block is xor-ed by the value shift[i].

Complexity :

We use centroid decomposition like this :

• Find a centroid
• Collect all queries in the given tree
• Apply given queries only to a path which pass the centroid
• Remove a centroid, and continue in each component (divide and conquer)

I think this step is kinda typical for most tree divide & conquer problem. So let's see how to do step 3. Say that centroid is C and there is a son v₁, v₂, ..., v_k. If a query (x, d) is derived from subtree of v_i, then it is applied to with value d - dist(x, C).

To make explaination easier we will just say it is applied to subtree(C) (it doesn't change significantly). We should sum up the value of max(0, d - dist(C, v)) for each vertex v. For fixed list can do it in O(lgn) time with binary search and partial sum.