2248D.md (3810B)
1 Source: https://codeforces.com/problemset/problem/2248/D 2 3 D. Good Pair Queries 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 two binary strings $s$ and $t$, both of length $n$. 22 23 For two binary strings $a$ and $b$ of the same length, the pair $(a, b)$ is called good if both strings can be made empty by performing the following operation zero or more times: 24 25 * Choose a non-empty set of positions $1 \le i_1 \lt i_2 \lt \ldots \lt i_k \le |a|$ and a character $c \in \{\mathtt{0}, \mathtt{1}\}$. 26 * Let $x = a_{i_1}a_{i_2}\ldots a_{i_k}$ and $y = b_{i_1}b_{i_2}\ldots b_{i_k}$. 27 * The character $c$ must be a mode$^{\text{∗}}$ of both $x$ and $y$. 28 * Delete the characters at the chosen positions from both strings. The remaining characters are concatenated without changing their relative order. 29 30 A binary string may have both $\mathtt{0}$ and $\mathtt{1}$ as modes. 31 32 You need to answer $q$ queries. In each query, you are given two integers $l$ and $r$. Determine whether the pair of substrings $(s_l s_{l+1} \ldots s_r, t_l t_{l+1} \ldots t_r)$ is good. 33 34 The queries are independent. 35 36 $^{\text{∗}}$For a binary string $z$, a character $c$ is a mode if it appears at least $\left\lceil \frac{|z|}{2} \right\rceil$ times in $z$. Here, $\lceil x \rceil$ denotes the smallest integer greater than or equal to $x$. 37 38 Input 39 40 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows. 41 42 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 each string and the number of queries. 43 44 The second line of each test case contains the binary string $s$ of length $n$. 45 46 The third line of each test case contains the binary string $t$ of length $n$. 47 48 Each of the next $q$ lines contains two integers $l$ and $r$ ($1 \le l \le r \le n$) — a query. 49 50 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 51 52 It is guaranteed that the sum of $q$ over all test cases does not exceed $2 \cdot 10^5$. 53 54 Output 55 56 For each query, output "YES" if the pair $(s_l s_{l+1} \ldots s_r, t_l t_{l+1} \ldots t_r)$ is good. Otherwise, output "NO". 57 58 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. 59 60 Example 61 62 Input 63 64 ``` 65 3 66 67 2 2 68 69 01 70 71 10 72 73 1 1 74 75 1 2 76 77 5 1 78 79 11111 80 81 11111 82 83 1 3 84 85 5 1 86 87 00011 88 89 01111 90 91 1 5 92 ``` 93 94 Output 95 96 ``` 97 NO 98 99 YES 100 101 YES 102 103 YES 104 ``` 105 106 Note 107 108 In the first test case, for the first query, the pair is $(\mathtt{0}, \mathtt{1})$. No character is a mode of both strings, so no operation can be performed. 109 110 For the second query, choose both positions and $c = \mathtt{0}$. Then $x = \mathtt{01}$ and $y = \mathtt{10}$, so $c$ is a mode of both strings and the whole pair is deleted. 111 112 In the third test case, neither character is a mode of both $\mathtt{00011}$ and $\mathtt{01111}$, so the whole pair cannot be deleted in one operation. It can be emptied in three operations: 113 114 * Choose positions $2$ and $4$ and $c = \mathtt{1}$. Then $x = \mathtt{01}$ and $y = \mathtt{11}$, so $c$ is a mode of both $x$ and $y$. After deleting the selected positions, the remaining characters are concatenated, giving the pair $(\mathtt{001}, \mathtt{011})$. 115 * Choose positions $1$ and $2$ and $c = \mathtt{0}$. Then $x = \mathtt{00}$ and $y = \mathtt{01}$, so $c$ is a mode of both $x$ and $y$. After deleting the selected positions, the pair becomes $(\mathtt{1}, \mathtt{1})$. 116 * Choose the remaining position $1$ and $c = \mathtt{1}$. Then $x = \mathtt{1}$ and $y = \mathtt{1}$, so $c$ is a mode of both $x$ and $y$. Deleting the selected position makes both strings empty.