310696: CF1872E. Data Structures Fan

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

E. Data Structures Fantime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

You are given an array of integers $a_1, a_2, \ldots, a_n$, as well as a binary string$^{\dagger}$ $s$ consisting of $n$ characters.

Augustin is a big fan of data structures. Therefore, he asked you to implement a data structure that can answer $q$ queries. There are two types of queries:

  • "1 $l$ $r$" ($1\le l \le r \le n$) — replace each character $s_i$ for $l \le i \le r$ with its opposite. That is, replace all $\texttt{0}$ with $\texttt{1}$ and all $\texttt{1}$ with $\texttt{0}$.
  • "2 $g$" ($g \in \{0, 1\}$) — calculate the value of the bitwise XOR of the numbers $a_i$ for all indices $i$ such that $s_i = g$. Note that the $\operatorname{XOR}$ of an empty set of numbers is considered to be equal to $0$.

Please help Augustin to answer all the queries!

For example, if $n = 4$, $a = [1, 2, 3, 6]$, $s = \texttt{1001}$, consider the following series of queries:

  1. "2 $0$" — we are interested in the indices $i$ for which $s_i = \tt{0}$, since $s = \tt{1001}$, these are the indices $2$ and $3$, so the answer to the query will be $a_2 \oplus a_3 = 2 \oplus 3 = 1$.
  2. "1 $1$ $3$" — we need to replace the characters $s_1, s_2, s_3$ with their opposites, so before the query $s = \tt{1001}$, and after the query: $s = \tt{0111}$.
  3. "2 $1$" — we are interested in the indices $i$ for which $s_i = \tt{1}$, since $s = \tt{0111}$, these are the indices $2$, $3$, and $4$, so the answer to the query will be $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}$, there are no indices with $s_i = \tt{1}$, so since the $\operatorname{XOR}$ of an empty set of numbers is considered to be equal to $0$, the answer to this query is $0$.

$^{\dagger}$ A binary string is a string containing only characters $\texttt{0}$ or $\texttt{1}$.

Input

The first line of the input contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases in the test.

The descriptions of the test cases follow.

The first line of each test case description contains an integer $n$ ($1 \le n \le 10^5$) — the length of the array.

The second line of the test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$).

The third line of the test case contains the binary string $s$ of length $n$.

The fourth line of the test case contains one integer $q$ ($1 \le q \le 10^5$) — the number of queries.

The subsequent $q$ lines of the test case describe the queries. The first number of each query, $tp \in \{1, 2\}$, characterizes the type of the query: if $tp = 1$, then $2$ integers $1 \le l \le r \le n$ follow, meaning that the operation of type $1$ should be performed with parameters $l, r$, and if $tp = 2$, then one integer $g \in \{0, 1\}$ follows, meaning that the operation of type $2$ should be performed with parameter $g$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$, and also that the sum of $q$ over all test cases does not exceed $10^5$.

Output

For each test case, and for each query of type $2$ in it, output the answer to the corresponding query.

ExampleInput
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
Output
3 2 6 7 7 
11 7 
0 0 
16430827 
47 
Note

Let's analyze the first test case:

  1. "2 $0$" — we are interested in the indices $i$ for which $s_i = \tt{0}$, since $s = \tt{01000}$, these are the indices $1, 3, 4$, and $5$, so the answer to the query will be $a_1 \oplus a_3 \oplus a_4 \oplus a_5 = 1 \oplus 3 \oplus 4 \oplus 5 = 3$.
  2. "2 $1$" — we are interested in the indices $i$ for which $s_i = \tt{1}$, since $s = \tt{01000}$, the only suitable index is $2$, so the answer to the query will be $a_2 = 2$.
  3. "1 $2$ $4$" — we need to replace the characters $s_2, s_3, s_4$ with their opposites, so before the query $s = \tt{01000}$, and after the query: $s = \tt{00110}$.
  4. "2 $0$" — we are interested in the indices $i$ for which $s_i = \tt{0}$, since $s = \tt{00110}$, these are the indices $1, 2$, and $5$, so the answer to the query will be $a_1 \oplus a_2 \oplus a_5 = 1 \oplus 2 \oplus 5 = 6$.
  5. "2 $1$" — we are interested in the indices $i$ for which $s_i = \tt{1}$, since $s = \tt{00110}$, these are the indices $3$ and $4$, so the answer to the query will be $a_3 \oplus a_4 = 3 \oplus 4 = 7$.
  6. "1 $1$ $3$" — $s = \tt{00110}$ $\to$ $s = \tt{11010}$.
  7. "2 $1$" — we are interested in the indices $i$ for which $s_i = \tt{1}$, since $s = \tt{11010}$, these are the indices $1, 2$, and $4$, so the answer to the query will be $a_1 \oplus a_2 \oplus a_4 = 1 \oplus 2 \oplus 4 = 7$.

Output

题目大意:

给定一个整数数组和一个长度相同的二进制字符串。支持两种操作:

1. 将二进制字符串中 [l, r] 位置的字符取反。
2. 计算数组中所有满足二进制字符串对应位置为 g 的元素的异或和。

输入输出数据格式:

输入:

第一行包含一个整数 t,表示测试案例的数量。

每个测试案例包含四部分:

1. 一个整数 n,表示数组长度。
2. n 个整数,表示数组元素。
3. 一个长度为 n 的二进制字符串。
4. 一个整数 q,表示操作数量。
5. q 行,每行表示一个操作,操作 1 包含三个整数,操作 2 包含两个整数。

输出:

对于每个测试案例中的每个操作 2,输出计算结果。题目大意: 给定一个整数数组和一个长度相同的二进制字符串。支持两种操作: 1. 将二进制字符串中 [l, r] 位置的字符取反。 2. 计算数组中所有满足二进制字符串对应位置为 g 的元素的异或和。 输入输出数据格式: 输入: 第一行包含一个整数 t,表示测试案例的数量。 每个测试案例包含四部分: 1. 一个整数 n,表示数组长度。 2. n 个整数,表示数组元素。 3. 一个长度为 n 的二进制字符串。 4. 一个整数 q,表示操作数量。 5. q 行,每行表示一个操作,操作 1 包含三个整数,操作 2 包含两个整数。 输出: 对于每个测试案例中的每个操作 2,输出计算结果。

加入题单

上一题 下一题 算法标签: