Deduction Queries
Contest: Lyft Level 5 Challenge 2018 - Final Round
Difficulty rating: 2400
Tags: data structures, dsu

There is an array $$$a$$$ of $$$2^{30}$$$ integers, indexed from $$$0$$$ to $$$2^{30}-1$$$. Initially, you know that $$$0 \leq a_i < 2^{30}$$$ ($$$0 \leq i < 2^{30}$$$), but you do not know any of the values. Your task is to process queries of two types:

- 1 l r x: You are informed that the bitwise xor of the subarray $$$[l, r]$$$ (ends inclusive) is equal to $$$x$$$. That is, $$$a_l \oplus a_{l+1} \oplus \ldots \oplus a_{r-1} \oplus a_r = x$$$, where $$$\oplus$$$ is the bitwise xor operator. In some cases, the received update contradicts past updates. In this case, you should ignore the contradicting update (the current update).
- 2 l r: You are asked to output the bitwise xor of the subarray $$$[l, r]$$$ (ends inclusive). If it is still impossible to know this value, considering all past updates, then output $$$-1$$$.

Note that the queries are encoded. That is, you need to write an online solution.

Input format:
The first line contains a single integer $$$q$$$ ($$$1 \leq q \leq 2 \cdot 10^5$$$) — the number of queries.

Each of the next $$$q$$$ lines describes a query. It contains one integer $$$t$$$ ($$$1 \leq t \leq 2$$$) — the type of query.

The given queries will be encoded in the following way: let $$$last$$$ be the answer to the last query of the second type that you have answered (initially, $$$last = 0$$$). If the last answer was $$$-1$$$, set $$$last = 1$$$.

- If $$$t = 1$$$, three integers follow, $$$l'$$$, $$$r'$$$, and $$$x'$$$ ($$$0 \leq l', r', x' < 2^{30}$$$), meaning that you got an update. First, do the following: $$$l = l' \oplus last$$$, $$$r = r' \oplus last$$$, $$$x = x' \oplus last$$$ and, if $$$l > r$$$, swap $$$l$$$ and $$$r$$$.This means you got an update that the bitwise xor of the subarray $$$[l, r]$$$ is equal to $$$x$$$ (notice that you need to ignore updates that contradict previous updates).
- If $$$t = 2$$$, two integers follow, $$$l'$$$ and $$$r'$$$ ($$$0 \leq l', r' < 2^{30}$$$), meaning that you got a query. First, do the following: $$$l = l' \oplus last$$$, $$$r = r' \oplus last$$$ and, if $$$l > r$$$, swap $$$l$$$ and $$$r$$$.For the given query, you need to print the bitwise xor of the subarray $$$[l, r]$$$. If it is impossible to know, print $$$-1$$$. Don't forget to change the value of $$$last$$$.

It is guaranteed there will be at least one query of the second type.

Output format:
After every query of the second type, output the bitwise xor of the given subarray or $$$-1$$$ if it is still impossible to know.

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

Note:
In the first example, the real queries (without being encoded) are:

- 12
- 2 1 2
- 2 0 1073741823
- 1 1 2 5
- 2 1 1
- 2 2 2
- 2 1 2
- 1 2 3 6
- 2 1 1
- 1 1 3 0
- 2 1 1
- 2 2 2
- 2 3 3

- The answers for the first two queries are $$$-1$$$ because we don't have any such information on the array initially.
- The first update tells us $$$a_1 \oplus a_2 = 5$$$. Note that we still can't be certain about the values $$$a_1$$$ or $$$a_2$$$ independently (for example, it could be that $$$a_1 = 1, a_2 = 4$$$, and also $$$a_1 = 3, a_2 = 6$$$).
- After we receive all three updates, we have enough information to deduce $$$a_1, a_2, a_3$$$ independently.

In the second example, notice that after the first two updates we already know that $$$a_5 \oplus a_6 = 12$$$, so the third update is contradicting, and we ignore it.

Example input:
12
2 1 2
2 1 1073741822
1 0 3 4
2 0 0
2 3 3
2 0 3
1 6 7 3
2 4 4
1 0 2 1
2 0 0
2 4 4
2 0 0

Example output:
-1
-1
-1
-1
5
-1
6
3
5

Example input:
4
1 5 5 9
1 6 6 5
1 6 5 10
2 6 5

Example output:
12

Editorial:
First, let's learn how to handle information we have not recieved in updates. Let the function $$$W(l, r)$$$ be equal to the xor of the subarray $$$[l, r]$$$. Also, we define $$$W(l, r) = W(r, l)$$$.
Assume 3 indicies $$$a \leq b \leq c$$$. There are 2 rules:
• $$$W(a, b) \oplus W(b + 1, c) = W(a, c)$$$.
• $$$W(a, c) \oplus W(b, c) = W(a, b - 1)$$$ (holds when $$$a < b$$$).
These rules require a lot of conditions (and also plenty of $$$\pm$$$ 1). We can simplify them greatly: Let's index the borders between cells in our array (there are $$$2^{30} + 1$$$ of them). Now, instead of defining a subarray $$$[l, r]$$$ by its 2 endpoint cells, we will define a subarray by its 2 endpoint borders. Technically it just means, that we should increase $$$r$$$ by 1, and then we get the 2 end borders.
From now I will assume that our input is given in such a way, that subarrays are defined by their borders (So I will not mention the addition of 1 to $$$r$$$). Notice that the function $$$W(l, r)$$$ is also affected by this.
If we take a look at our rules again, they boil down to just 1 rule:
• $$$W(a, b) \oplus W(b, c) = W(a, c)$$$, for any 3 indicies $$$a,b,c$$$ ($$$a \leq b \leq c$$$ doesn't need to hold now, for instance $$$W(3, 5) \oplus W(5, 2) = W(3, 2)$$$).
This transformation also shows an observation; Assume every border is a vertex in a graph, and every update $$$W(l, r) = x$$$ describes an undirected edge between the vertices $$$l, r$$$ with weight $$$x$$$. We let the distance between 2 nodes $$$a, b$$$ be the xor of edge weights on the path between them. Notice that this distance is equal to $$$W(a, b)$$$. In other words, an update adds an edge and a query asks for some distance.
Another observation is that, we do not care about all the $$$2^{30} + 1$$$ nodes, but only about the ones we recieved in queries and updates. Moreover, their order is irrelevant, so we can do an online mapping of new nodes to the next free indicies. Thus, the number of nodes will be worstcase $$$\mathcal{O}(q)$$$.
Claim: We can know the answer to some query $$$[l, r]$$$, if and only if there exists a path between the nodes $$$l, r$$$ (they are in the same connected component).
//start spoiler of proof
There will be some subset of edges we take, to form the xor between nodes $$$l$$$ and $$$r$$$. Assume every vertex has 2 states, on/off. Initially all vertices are off, and our current answer is $$$0$$$. When we take an edge we flip the state of its 2 ends, and xor our answer by its weight. Suppose at some moment of time the nodes with "on" state are {$$$x_0, x_1, x_2, ..., x_k$$$} (in sorted order). Observe that our current answer is equal to $$$W(x_0, x_1) \oplus W(x_2, x_3) \oplus \ldots \oplus W(x_{k-1}, x_k)$$$. This implies we want our subset of edges to end up having only the nodes {$$$l, r$$$} activated. We look at the connected components. Observe that in each connected component, the number of nodes activated at any time is even. If the nodes $$$l$$$ and $$$r$$$ are in different component, then in our final result we would want to have only 1 activated node in the component of $$$l$$$, and same with $$$r$$$, but this is impossible.
//end spoiler of proof
First, we need to know whether a query gives us 2 nodes that are in different components (to know whether the answer is $$$-1$$$ or not). For this we need to use the Union-Find structure. Also notice, that our Union-Find structure will only need to handle a forest of trees (if an update gives us an edge that creates a cycle, it means there is no contribution, so we ignore it).
Provided that an answer does exist, we need to also handle finding a xor path between 2 nodes in a tree, and to support merging of trees. Generally to find a property over some path in a tree, it is common to use LCA or binary lifting. This turns out very difficult when we also need to merge trees (unless you insist on implementing Link-Cut/ETT). Fortunately, we can still abuse the xor operator. In some tree, mark $$$x_v$$$ as the xor of edges on the path from $$$v$$$ to some arbitrary root in the tree. The xor path between nodes ($$$u, v$$$) turns out to be $$$x_u \oplus x_v$$$. So we would like to maintain for each tree some arbitrary root and all those values.
Notice that we can augment our Union-Find structure to support this as well: For each node $$$v$$$ in the structure, we maintain $$$p_v$$$ as its parent in the structure, and $$$x_v$$$ as the xor on the path from $$$v$$$ to $$$p_v$$$. Notice that $$$x_v$$$ can be easily updated together with $$$p_v$$$ during the $$$find()$$$ operation in the structure.
To summarize, when we are given $$$W(l, r) = x$$$ in some update, we transform it to $$$W(p_l, p_r) = x \oplus x_l \oplus x_r$$$, and then we add the edge between the parents.
Finally, the complexity is $$$\mathcal{O}(q \log{q})$$$, but this is only due to the online mapping if we use a regular map; You can use a hash table and get a running time of $$$\mathcal{O}(q \times \alpha(q))$$$, but I suggest being careful with a hash table (you may want to read this: https://codeforces.com/blog/entry/62393).