← 返回题目列表

Codeforces · 1872/E

E. 数据结构风扇

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

给定一个整数数组 $$$a_1, a_2, \ldots, a_n$$$,以及一个由 $$$n$$$ 字符组成的二进制字符串$$$^{\dagger}$$$ $$$s$$$。

Augustin 是数据结构的忠实粉丝。因此,他要求你实现一个可以回答 $$$q$$$ 查询的数据结构。有两种类型的查询:

- "1 $$$l$$$ $$$r$$$" ($$$1\le l \le r \le n$$$) — 将 $$$l \le i \le r$$$ 的每个字符 $$$s_i$$$ 替换为其相反字符。也就是说,将所有 $$$\texttt{0}$$$ 替换为 $$$\texttt{1}$$$,并将所有 $$$\texttt{1}$$$ 替换为 $$$\texttt{0}$$$。
- "2 $$$g$$$" ($$$g \in \{0, 1\}$$$) - 计算所有索引 $$$i$$$ 的数字 $$$a_i$$$ 按位异或的值,使得 $$$s_i = g$$$。请注意,空数字集的 $$$\operatorname{XOR}$$$ 被视为等于 $$$0$$$。

请帮助奥古斯丁回答所有疑问!

例如,如果 $$$n = 4$$$、$$$a = [1, 2, 3, 6]$$$、$$$s = \texttt{1001}$$$,请考虑以下一系列查询:

1. "2 $$$0$$$" - 我们感兴趣的是索引 $$$i$$$,其中 $$$s_i = \tt{0}$$$,因为 $$$s = \tt{1001}$$$,这些是索引 $$$2$$$ 和 $$$3$$$,因此查询的答案将是 $$$a_2 \oplus a_3 = 2 \oplus 3 = 1$$$。
2. "1 $$$1$$$ $$$3$$$" - 我们需要将字符 $$$s_1, s_2, s_3$$$ 替换为它们的反义词,因此在查询之前 $$$s = \tt{1001}$$$,在查询之后:$$$s = \tt{0111}$$$。
3. "2 $$$1$$$" - 我们对索引 $$$i$$$ 感兴趣,其中 $$$s_i = \tt{1}$$$,因为 $$$s = \tt{0111}$$$,这些是索引 $$$2$$$、$$$3$$$ 和 $$$4$$$,因此查询的答案将是$$$a_2 \oplus a_3 \oplus a_4 = 2 \oplus 3 \oplus 6 = 7$$$。
4. "1 $$$2$$$ $$$4$$$" — $$$s = \tt{0111}$$$ $$$\to$$$ $$$s = \tt{0000}$$$。
5. "2 $$$1$$$" — $$$s = \tt{0000}$$$,没有 $$$s_i = \tt{1}$$$ 的索引,因此由于空数字集的 $$$\operatorname{XOR}$$$ 被认为等于 $$$0$$$,因此该查询的答案是 $$$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$$$,则后面跟着 $$$2$$$ 整数 $$$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

5
5
1 2 3 4 5
01000
7
2 0
2 1
1 2 4
2 0
2 1
1 1 3
2 1
6
12 12 14 14 5 5
001001
3
2 1
1 2 4
2 1
4
7 7 7 777
1111
3
2 0
1 2 3
2 0
2
1000000000 996179179
11
1
2 1
5
1 42 20 47 7
00011
5
1 3 4
1 1 1
1 3 4
1 2 4
2 0

输出 #1

3 2 6 7 7 
11 7 
0 0 
16430827 
47

注意

我们来分析第一个测试用例:

1. "2 $$$0$$$" - 我们对索引 $$$i$$$ 感兴趣,其中 $$$s_i = \tt{0}$$$,因为 $$$s = \tt{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 = \tt{1}$$$ 的索引 $$$i$$$ 感兴趣,因为 $$$s = \tt{01000}$$$,唯一合适的索引是 $$$2$$$,因此查询的答案将是 $$$a_2 = 2$$$。
3. "1 $$$2$$$ $$$4$$$" — 我们需要将字符 $$$s_2, s_3, s_4$$$ 替换为它们的反义词,因此在查询之前 $$$s = \tt{01000}$$$,在查询之后:$$$s = \tt{00110}$$$。
4. "2 $$$0$$$" - 我们对索引 $$$i$$$ 感兴趣,其中 $$$s_i = \tt{0}$$$,因为 $$$s = \tt{00110}$$$,这些是索引 $$$1、2$$$ 和 $$$5$$$,因此查询的答案将为 $$$a_1 \oplus a_2 \oplus a_5 = 1 \oplus 2 \oplus 5 = 6$$$。
5. "2 $$$1$$$" - 我们对索引 $$$i$$$ 感兴趣,其中 $$$s_i = \tt{1}$$$,因为 $$$s = \tt{00110}$$$,这些是索引 $$$3$$$ 和 $$$4$$$,因此查询的答案将是 $$$a_3 \oplus a_4 = 3 \oplus 4 = 7$$$。
6. "1 $$$1$$$ $$$3$$$" — $$$s = \tt{00110}$$$ $$$\to$$$ $$$s = \tt{11010}$$$。
7. "2 $$$1$$$" - 我们对索引 $$$i$$$ 感兴趣,其中 $$$s_i = \tt{1}$$$,因为 $$$s = \tt{11010}$$$,这些是索引 $$$1、2$$$ 和 $$$4$$$,因此查询的答案将为 $$$a_1 \oplus a_2 \oplus a_4 = 1 \oplus 2 \oplus 4 = 7$$$。