Deduction Queries
题意翻译
q此操作$(1 \leq q \leq 2 \times 10^5)$,两种操作类型:
1,l,r,x:表示l到r的异或和为x;
2,l,r:表示询问l到r的异或和。
强制在线。$(0 \leq l,r,x \leq 2^{30})$
题目描述
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.
输入输出格式
输入格式
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.
输出格式
After every query of the second type, output the bitwise xor of the given subarray or $ -1 $ if it is still impossible to know.
输入输出样例
输入样例 #1
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
输出样例 #1
-1
-1
-1
-1
5
-1
6
3
5
输入样例 #2
4
1 5 5 9
1 6 6 5
1 6 5 10
2 6 5
输出样例 #2
12
说明
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.