CF2217D Flip the Bit (Hard Version)

这是本题的困难版本。不同版本的区别在于，本题中可能存在多个特殊下标（$1 \le k \le n$）。只有当你完成所有版本的本题后才能进行 hack。 给定一个长度为 $n$ 的二进制数组 $a$ ，以及 $k$ 个特殊下标 $p_1, p_2, \ldots, p_k$（$1 \le p_i \le n$）。已知所有特殊下标上的元素值都相同（即 $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 k \le n \le 2 \cdot 10^5$），分别表示数组长度和特殊下标数量。 第二行包含 $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 < p_2 < \ldots < p_k \le n$），表示特殊下标。保证 $a_{p_1} = a_{p_2} = \ldots = a_{p_k}$。 保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一个整数，表示最少需要的操作次数。

对于第一个测试用例，可以选择区间 $[1, 2]$，翻转两个元素，得到 $[0, 1]$。接着选择区间 $[1, 1]$，翻转第一个元素得到 $[1, 1]$。 对于第二个测试用例，可以选择区间 $[1, 2]$，翻转两个元素得到 $[1, 0, 0]$。然后选择区间 $[1, 1]$，翻转第一个元素得到 $[0, 0, 0]$。 对于第四个测试用例，可以选择区间 $[2, 8]$，翻转这些元素得到 $[0, 0, 1, 1, 0, 1, 1, 0, 0]$。然后选择区间 $[3, 4]$，翻转得到 $[0, 0, 0, 0, 0, 1, 1, 0, 0]$。再选区间 $[6, 7]$，翻转得到 $[0, 0, 0, 0, 0, 0, 0, 0, 0]$。虽然也有其他方式，但可以证明最少需要 $3$ 次操作。 由 ChatGPT 5 翻译