2217B.md (2385B)
1 Source: https://codeforces.com/problemset/problem/2217/B 2 3 B. Flip the Bit (Easy Version) 4 5 time limit per test 6 7 1.5 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 This is the easy version of the problem. The difference between the versions is that in this version, there is exactly one special index ($k=1$). You can hack only if you solved all versions of this problem. 22 23 You are given a binary array $a$ of length $n$ and $k$ special indices $p_1, p_2, \ldots, p_k$ ($1 \le p_i \le n$). It is given that the values $a_i$ of all elements at special indices are the same (i. e., $a_{p_1} = a_{p_2} = \ldots = a_{p_k}$). 24 25 In one operation, you can choose a range $[l, r]$ ($1 \le l \le r \le n$) such that the range contains at least one special index ($l \le p_i \le r$) and flip all bits $a_j$ for $l \le j \le r$. Flipping a bit changes $0$ to $1$ and $1$ to $0$. 26 27 Let $x$ denote the value at special indices before any operations are applied. Find the minimum number of operations required to make all elements of the array equal to $x$. 28 29 Input 30 31 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. 32 33 The first line of each test case contains two integers $n$ and $k$ ($1 \le n \le 2 \cdot 10^5$; $k=1$) — the length of the array and the number of special indices. 34 35 The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 1$) — the elements of the array. 36 37 The third line contains $k$ integers $p_1, p_2, \ldots, p_k$ ($1 \le p_1 \lt p_2 \lt \ldots \lt p_k \le n$) — the special indices. It is guaranteed that $a_{p_1} = a_{p_2} = \ldots = a_{p_k}$. 38 39 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 40 41 Output 42 43 For each test case, output a single integer — the minimum number of operations required. 44 45 Example 46 47 Input 48 49 ``` 50 4 51 52 3 1 53 54 0 1 0 55 56 2 57 58 5 1 59 60 1 1 1 1 1 61 62 1 63 64 6 1 65 66 0 1 0 1 0 1 67 68 3 69 70 17 1 71 72 0 1 1 0 1 1 0 1 0 0 1 0 1 0 1 0 1 73 74 5 75 ``` 76 77 Output 78 79 ``` 80 2 81 82 0 83 84 4 85 86 10 87 ``` 88 89 Note 90 91 For the first test case, you can choose the range $[1, 3]$ and flip all the bits to get $[1, 0, 1]$. Then you can choose the range $[2, 2]$ and flip the second bit to get $[1, 1, 1]$. 92 93 For the second test case, all the bits already match the value at the special index. You do not need any operations.