2244E.md (2241B)
1 Source: https://codeforces.com/problemset/problem/2244/E 2 3 E. Masha and the Garland 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 Masha has a New Year garland consisting of $n$ bulbs. Each bulb can be either off or on. The state of the garland is given by a binary string $s$ of length $n$, where '0' denotes an off bulb and '1' denotes an on bulb. 22 23 Masha considers the garland beautiful if the states of adjacent bulbs strictly alternate. That is, there are no two adjacent bulbs that are both on or both off. For example, the garlands '01010' and '1010' are beautiful, while '0110' and '000' are not. 24 25 Yura can apply the following operation to the garland: choose a subsegment and flip the state of all bulbs in it, that is, turn all on bulbs off and all off bulbs on. 26 27 Masha invites him to play the following game $q$ times: she chooses a segment from the $l$-th to the $r$-th bulb inclusive, and Yura must make this segment beautiful using at most $k$ operations. 28 29 However, Yura is not sure whether this is always possible, so he asks you to determine for each game whether he can make the chosen segment beautiful using no more than $k$ operations. Note that the games are independent, and the garland itself is not actually modified. 30 31 Input 32 33 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. 34 35 The first line of each test case contains two integers $n$ and $q$ ($1 \le n, q \le 2 \cdot 10^5$) — the length of the garland and the number of games. 36 37 The second line contains a binary string $s$ of length $n$, consisting only of characters '0' and '1'. 38 39 The next $q$ lines each contain three integers $l$, $r$, and $k$ ($1 \le l \le r \le n$, $0 \le k \le n$) — the boundaries of the segment and the maximum allowed number of operations. 40 41 It is guaranteed that the sum of $n$ and the sum of $q$ over all test cases do not exceed $2 \cdot 10^5$. 42 43 Output 44 45 For each game, output "YES" if the segment can be made beautiful using at most $k$ operations, and "NO" otherwise. 46 47 Example 48 49 Input 50 51 ``` 52 2 53 54 5 5 55 56 00110 57 58 1 5 1 59 60 1 5 2 61 62 2 4 1 63 64 1 2 0 65 66 3 4 0 67 68 4 2 69 70 1010 71 72 1 4 0 73 74 2 3 1 75 ``` 76 77 Output 78 79 ``` 80 YES 81 82 YES 83 84 YES 85 86 NO 87 88 NO 89 90 YES 91 92 YES 93 ```