Это сложная версия задачи. Отличие между версиями заключается в том, что в этой версии может быть несколько специальных индексов ($$$1 \le k \le n$$$). Вы можете делать взломы только в том случае, если решили все версии этой задачи.
Дан бинарный массив $$$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 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 \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$$$.
Для каждого набора входных данных выведите одно целое число — минимальное количество операций, необходимое для решения задачи.
62 11 013 20 1 01 35 51 1 1 1 11 2 3 4 59 50 1 0 0 1 0 0 1 03 4 6 7 913 41 0 0 1 0 1 0 1 1 0 1 0 14 8 11 1315 31 0 1 0 1 0 1 0 1 0 1 0 1 0 13 11 13
220358
Для первого набора входных данных можно выбрать отрезок $$$[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$$$.
