CF1044D Deduction Queries

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.

N/A

N/A

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.