codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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$.