2036C.md (2020B)
1 Source: https://codeforces.com/problemset/problem/2036/C 2 3 C. Anya and 1100 4 5 time limit per test 6 7 3 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 While rummaging through things in a distant drawer, Anya found a beautiful string $s$ consisting only of zeros and ones. 22 23 Now she wants to make it even more beautiful by performing $q$ operations on it. 24 25 Each operation is described by two integers $i$ ($1 \le i \le |s|$) and $v$ ($v \in \{0, 1\}$) and means that the $i$-th character of the string is assigned the value $v$ (that is, the assignment $s_i = v$ is performed). 26 27 But Anya loves the number $1100$, so after each query, she asks you to tell her whether the substring "1100" is present in her string (i.e. there exist such $1 \le i \le |s| - 3$ that $s_{i}s_{i + 1}s_{i + 2}s_{i + 3} = \texttt{1100}$). 28 29 Input 30 31 The first line contains one integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. 32 33 The first line of the test case contains the string $s$ ($1 \leq |s| \leq 2 \cdot 10^5$), consisting only of the characters "0" and "1". Here $|s|$ denotes the length of the string $s$. 34 35 The next line contains an integer $q$ ($1 \leq q \leq 2 \cdot 10^5$) — the number of queries. 36 37 The following $q$ lines contain two integers $i$ ($1 \leq i \leq |s|$) and $v$ ($v \in \{0, 1\}$), describing the query. 38 39 It is guaranteed that the sum of $|s|$ across all test cases does not exceed $2 \cdot 10^5$. It is also guaranteed that the sum of $q$ across all test cases does not exceed $2 \cdot 10^5$. 40 41 Output 42 43 For each query, output "YES", if "1100" is present in Anya's string; otherwise, output "NO". 44 45 You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses. 46 47 Example 48 49 Input 50 51 ``` 52 4 53 54 100 55 56 4 57 58 1 1 59 60 2 0 61 62 2 0 63 64 3 1 65 66 1100000 67 68 3 69 70 6 1 71 72 7 1 73 74 4 1 75 76 111010 77 78 4 79 80 1 1 81 82 5 0 83 84 4 1 85 86 5 0 87 88 0100 89 90 4 91 92 3 1 93 94 1 1 95 96 2 0 97 98 2 1 99 ``` 100 101 Output 102 103 ``` 104 NO 105 NO 106 NO 107 NO 108 YES 109 YES 110 NO 111 NO 112 YES 113 YES 114 YES 115 NO 116 NO 117 NO 118 NO 119 ```