← 返回题目列表

Codeforces · 1044/D

D. 扣除查询

中文机器翻译题面 查看原题

有一个由 $$$2^{30}$$$ 整数组成的数组 $$$a$$$,索引从 $$$0$$$ 到 $$$2^{30}-1$$$。最初,您知道 $$$0 \leq a_i < 2^{30}$$$ ($$$0 \leq i < 2^{30}$$$),但您不知道任何值。您的任务是处理两种类型的查询:

- 1 l r x:您被告知子数组$$$[l, r]$$$(含)的按位异或等于$$$x$$$。即 $$$a_l \oplus a_{l+1} \oplus \ldots \oplus a_{r-1} \oplus a_r = x$$$,其中 $$$\oplus$$$ 是按位异或运算符。在某些情况下,收到的更新与过去的更新相矛盾。在这种情况下,您应该忽略矛盾的更新(当前更新)。
- 2 l r:要求您输出子数组 $$$[l, r]$$$(包含末尾)的按位异或。如果考虑到所有过去的更新仍然无法知道这个值,则输出$$$-1$$$。

请注意,查询是经过编码的。也就是说,你需要写一个在线解决方案。

输入

第一行包含一个整数 $$$q$$$ ($$$1 \leq q \leq 2 \cdot 10^5$$$) — 查询数。

接下来的 $$$q$$$ 行描述一个查询。它包含一个整数 $$$t$$$ ($$$1 \leq t \leq 2$$$) — 查询类型。

给定的查询将按以下方式编码:令 $$$last$$$ 为您已回答的第二种类型的最后一个查询的答案(最初,$$$last = 0$$$)。如果最后的答案是 $$$-1$$$,则设置 $$$last = 1$$$。

- 如果 $$$t = 1$$$,则后面跟着三个整数:$$$l'$$$、$$$r'$$$ 和 $$$x'$$$ ($$$0 \leq l', r', x' < 2^{30}$$$),表示您已获得更新。首先,执行以下操作: $$$l = l' \oplus last$$$、$$$r = r' \oplus last$$$、$$$x = x' \oplus last$$$ 并且,如果 $$$l > r$$$,则交换 $$$l$$$ 和 $$$r$$$。这意味着您得到了子数组 $$$[l, r]$$$ 的按位异或等于 $$$x$$$ 的更新(请注意,您需要忽略与先前更新相矛盾的更新)。
- 如果 $$$t = 2$$$,则后面跟着两个整数,$$$l'$$$ 和 $$$r'$$$ ($$$0 \leq l', r' < 2^{30}$$$),这意味着您有一个查询。首先,执行以下操作: $$$l = l' \oplus last$$$、$$$r = r' \oplus last$$$,并且如果 $$$l > r$$$,则交换 $$$l$$$ 和 $$$r$$$。对于给定的查询,您需要打印子数组 $$$[l, r]$$$ 的按位异或。如果无法知道,请打印 $$$-1$$$。不要忘记更改 $$$last$$$ 的值。

保证至少有一个第二类型的查询。

输出

在每次第二类型查询后,输出给定子数组的按位异或,如果仍然无法知道,则输出 $$$-1$$$ 。

示例

输入 #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

注意

在第一个示例中,真实查询(未经编码)是:

- 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

- 前两个查询的答案是 $$$-1$$$ 因为我们最初在数组上没有任何此类信息。
- 第一次更新告诉我们 $$$a_1 \oplus a_2 = 5$$$。请注意,我们仍然无法独立确定值 $$$a_1$$$ 或 $$$a_2$$$(例如,可能 $$$a_1 = 1,a_2 = 4$$$,也可能 $$$a_1 = 3,a_2 = 6$$$)。
- 在我们收到所有三个更新后,我们有足够的信息来独立推断 $$$a_1、a_2、a_3$$$。

在第二个例子中,请注意,在前两次更新之后,我们已经知道 $$$a_5 \oplus a_6 = 12$$$,因此第三次更新是矛盾的,我们忽略它。