CF1872E Data Structures Fan

给定一个整数数组 $a_1, a_2, \ldots, a_n$，以及一个长度为 $n$ 的二进制字符串 $s$（$^\dagger$）。 Augustin 非常喜欢数据结构，因此他让你实现一个数据结构来回答 $q$ 个查询。查询有两种类型： - “1 $l$ $r$”（$1 \le l \le r \le n$）——将 $s$ 中第 $l$ 到第 $r$ 个字符全部取反。即，将所有 $\texttt{0}$ 变为 $\texttt{1}$，所有 $\texttt{1}$ 变为 $\texttt{0}$。 - “2 $g$”（$g \in \{0, 1\}$）——计算所有满足 $s_i = g$ 的 $a_i$ 的按位异或（bitwise XOR）值。注意，空集的 $\operatorname{XOR}$ 被认为是 $0$。 请你帮助 Augustin 回答所有的查询！ 例如，若 $n = 4$，$a = [1, 2, 3, 6]$，$s = \texttt{1001}$，考虑如下查询序列： 1. “2 $0$”——我们关注 $s_i = \texttt{0}$ 的下标。此时 $s = \texttt{1001}$，对应下标为 $2$ 和 $3$，因此答案为 $a_2 \oplus a_3 = 2 \oplus 3 = 1$。 2. “1 $1$ $3$”——将 $s_1, s_2, s_3$ 取反，$s$ 由 $\texttt{1001}$ 变为 $\texttt{0111}$。 3. “2 $1$”——关注 $s_i = \texttt{1}$ 的下标。此时 $s = \texttt{0111}$，下标为 $2, 3, 4$，答案为 $a_2 \oplus a_3 \oplus a_4 = 2 \oplus 3 \oplus 6 = 7$。 4. “1 $2$ $4$”——$s = \texttt{0111}$ 变为 $s = \texttt{0000}$。 5. “2 $1$”——$s = \texttt{0000}$，没有 $s_i = \texttt{1}$ 的下标，因此答案为 $0$。 $^\dagger$ 二进制字符串指仅包含 $\texttt{0}$ 和 $\texttt{1}$ 的字符串。

输入的第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 10^5$），表示数组的长度。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$）。 第三行包含一个长度为 $n$ 的二进制字符串 $s$。 第四行包含一个整数 $q$（$1 \le q \le 10^5$），表示查询的数量。 接下来的 $q$ 行，每行描述一个查询。每个查询的第一个数字 $tp \in \{1, 2\}$ 表示查询类型：若 $tp = 1$，则后面有两个整数 $1 \le l \le r \le n$，表示执行类型 $1$ 的操作，参数为 $l, r$；若 $tp = 2$，则后面有一个整数 $g \in \{0, 1\}$，表示执行类型 $2$ 的操作，参数为 $g$。 保证所有测试用例中 $n$ 的总和不超过 $10^5$，所有测试用例中 $q$ 的总和不超过 $10^5$。

对于每个测试用例中的每个类型 $2$ 的查询，输出对应的答案。

我们来分析第一个测试用例： 1. “2 $0$”——我们关注 $s_i = \texttt{0}$ 的下标。此时 $s = \texttt{01000}$，下标为 $1, 3, 4, 5$，答案为 $a_1 \oplus a_3 \oplus a_4 \oplus a_5 = 1 \oplus 3 \oplus 4 \oplus 5 = 3$。 2. “2 $1$”——关注 $s_i = \texttt{1}$ 的下标。此时 $s = \texttt{01000}$，只有下标 $2$，答案为 $a_2 = 2$。 3. “1 $2$ $4$”——将 $s_2, s_3, s_4$ 取反，$s$ 由 $\texttt{01000}$ 变为 $\texttt{00110}$。 4. “2 $0$”——关注 $s_i = \texttt{0}$ 的下标。此时 $s = \texttt{00110}$，下标为 $1, 2, 5$，答案为 $a_1 \oplus a_2 \oplus a_5 = 1 \oplus 2 \oplus 5 = 6$。 5. “2 $1$”——关注 $s_i = \texttt{1}$ 的下标。此时 $s = \texttt{00110}$，下标为 $3, 4$，答案为 $a_3 \oplus a_4 = 3 \oplus 4 = 7$。 6. “1 $1$ $3$”——$s = \texttt{00110}$ 变为 $s = \texttt{11010}$。 7. “2 $1$”——关注 $s_i = \texttt{1}$ 的下标。此时 $s = \texttt{11010}$，下标为 $1, 2, 4$，答案为 $a_1 \oplus a_2 \oplus a_4 = 1 \oplus 2 \oplus 4 = 7$。 由 ChatGPT 4.1 翻译