← 返回题目列表

Codeforces · 2217/B

B. 翻转位(简易版)

中文机器翻译题面 查看原题

这是问题的简单版本。版本之间的区别在于,在这个版本中,只有一个特殊索引($$$k=1$$$)。只有解决了该问题的所有版本,您才能破解。

给定一个二进制数组 $$$a$$$,长度为 $$$n$$$ 和 $$$k$$$ 特殊指数 $$$p_1、p_2、\ldots、p_k$$$ ($$$1 \le p_i \le n$$$)。假设特殊索引处所有元素的值 $$$a_i$$$ 相同(即 $$$a_{p_1} = a_{p_2} = \ldots = a_{p_k}$$$)。

在一次操作中,您可以选择一个范围 $$$[l, r]$$$ ($$$1 \le l \le r \le n$$$),使得该范围包含 至少 一个特殊索引 ($$$l \le p_i \le r$$$) 并翻转 $$$a_j$$$ 的所有位 $$$l \le j \le r$$$。翻转一点会将 $$$0$$$ 更改为 $$$1$$$,将 $$$1$$$ 更改为 $$$0$$$。

让 $$$x$$$ 表示特殊索引处的值 在应用任何操作之前。求生成数组所有元素所需的最少操作次数 等于 $$$x$$$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$; $$$k=1$$$) — 数组的长度和特殊索引的数量。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 1$$$) — 数组的元素。

第三行包含 $$$k$$$ 整数 $$$p_1, p_2, \ldots, p_k$$$ ($$$1 \le p_1 \lt p_2 \lt \ldots \lt p_k \le n$$$) — 特殊索引。保证 $$$a_{p_1} = a_{p_2} = \ldots = a_{p_k}$$$。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数 - 所需的最小操作数。

示例

输入
复制

4
3 1
0 1 0
2
5 1
1 1 1 1 1
1
6 1
0 1 0 1 0 1
3
17 1
0 1 1 0 1 1 0 1 0 0 1 0 1 0 1 0 1
5

输出
复制

2
0
4
10

注意

对于第一个测试用例,您可以选择范围 $$$[1, 3]$$$ 并翻转所有位以获得 $$$[1, 0, 1]$$$。然后您可以选择范围$$$[2, 2]$$$并翻转第二位以获得$$$[1, 1, 1]$$$。

对于第二个测试用例,所有位都已与特殊索引处的值匹配。您不需要任何操作。