1872E.md (5099B)
1 Source: https://codeforces.com/problemset/problem/1872/E 2 3 E. Data Structures Fan 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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. 22 23 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: 24 25 * "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}$. 26 * "2 $g$" ($g \in \{0, 1\}$) — calculate the value of the [bitwise XOR](https://en.wikipedia.org/wiki/Bitwise_operation#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$. 27 28 Please help Augustin to answer all the queries! 29 30 For example, if $n = 4$, $a = [1, 2, 3, 6]$, $s = \texttt{1001}$, consider the following series of queries: 31 32 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$. 33 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}$. 34 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$. 35 4. "1 $2$ $4$" — $s = \tt{0111}$ $\to$ $s = \tt{0000}$. 36 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$. 37 38 $^{\dagger}$ A binary string is a string containing only characters $\texttt{0}$ or $\texttt{1}$. 39 40 Input 41 42 The first line of the input contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases in the test. 43 44 The descriptions of the test cases follow. 45 46 The first line of each test case description contains an integer $n$ ($1 \le n \le 10^5$) — the length of the array. 47 48 The second line of the test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$). 49 50 The third line of the test case contains the binary string $s$ of length $n$. 51 52 The fourth line of the test case contains one integer $q$ ($1 \le q \le 10^5$) — the number of queries. 53 54 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$. 55 56 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$. 57 58 Output 59 60 For each test case, and for each query of type $2$ in it, output the answer to the corresponding query. 61 62 Example 63 64 Input 65 66 ``` 67 5 68 69 5 70 71 1 2 3 4 5 72 73 01000 74 75 7 76 77 2 0 78 79 2 1 80 81 1 2 4 82 83 2 0 84 85 2 1 86 87 1 1 3 88 89 2 1 90 91 6 92 93 12 12 14 14 5 5 94 95 001001 96 97 3 98 99 2 1 100 101 1 2 4 102 103 2 1 104 105 4 106 107 7 7 7 777 108 109 1111 110 111 3 112 113 2 0 114 115 1 2 3 116 117 2 0 118 119 2 120 121 1000000000 996179179 122 123 11 124 125 1 126 127 2 1 128 129 5 130 131 1 42 20 47 7 132 133 00011 134 135 5 136 137 1 3 4 138 139 1 1 1 140 141 1 3 4 142 143 1 2 4 144 145 2 0 146 ``` 147 148 Output 149 150 ``` 151 3 2 6 7 7 152 11 7 153 0 0 154 16430827 155 47 156 ``` 157 158 Note 159 160 Let's analyze the first test case: 161 162 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$. 163 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$. 164 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}$. 165 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$. 166 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$. 167 6. "1 $1$ $3$" — $s = \tt{00110}$ $\to$ $s = \tt{11010}$. 168 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$.