CF2217D.Flip the Bit (Hard Version)

This is the hard version of the problem. The difference between the versions is that in this version, there can be multiple special indices ( $ 1 \le k \le n $ ). You can hack only if you solved all versions of this problem.

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} $ ).

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 $ .

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 $ .

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.

The first line of each test case contains two integers $ n $ and $ k $ ( $ 1 \le k \le n \le 2 \cdot 10^5 $ ) — the length of the array and the number of special indices.

The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 0 \le a_i \le 1 $ ) — the elements of the array.

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} $ .

It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

For each test case, output a single integer — the minimum number of operations required.

For the first test case, you can choose the range $ [1, 2] $ and flip both the bits to get $ [0, 1] $ . Then you can choose the range $ [1, 1] $ and flip the first bit to get $ [1, 1] $ .

For the second test case, you can choose the range $ [1, 2] $ and flip the bits to get $ [1, 0, 0] $ . Then you can choose the range $ [1, 1] $ and flip the first bit to get $ [0, 0, 0] $ .

For the fourth test case, you can choose the range $ [2, 8] $ and flip the bits to get $ [0, 0, 1, 1, 0, 1, 1, 0, 0] $ . Then you can choose the range $ [3, 4] $ and flip the bits to get $ [0, 0, 0, 0, 0, 1, 1, 0, 0] $ . Then you can choose the range $ [6, 7] $ and flip the bits to get $ [0, 0, 0, 0, 0, 0, 0, 0, 0] $ . Note that, while there can be other ways to achieve this, it can be proved that the minimum number of operations is $ 3 $ .