CF1044D Deduction Queries

有一个长度为 $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$。

在第一个样例中，真实的（未编码的）查询如下： - 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$，所以第三次更新与之前的信息矛盾，应予以忽略。 由 ChatGPT 4.1 翻译