Code: Flip the Bit (Hard Version)

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n, k;
    cin >> n >> k;

    vector<int> a(n + 1), p(k + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= k; ++i) cin >> p[i];

    const int x = a[p[1]];

    vector<int> odd(n + 1, 0);
    odd[0] = a[1] ^ x;
    for (int i = 1; i < n; ++i) odd[i] = a[i] ^ a[i + 1];
    odd[n] = a[n] ^ x;

    vector<int> cnt(k + 1, 0);
    int totalOdd = 0;
    int level = 0;
    int ptr = 1;

    for (int i = 0; i <= n; ++i) {
        while (ptr <= k && p[ptr] <= i) {
            ++level;
            ++ptr;
        }
        if (odd[i]) {
            ++cnt[level];
            ++totalOdd;
        }
    }

    int best = totalOdd / 2;
    for (int c : cnt) best = max(best, c);
    cout << best << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int N, K;
    cin >> N >> K;
    vector<int> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    vector<int> locs;
    locs.push_back(0);
    for (int i = 0; i < K; i++) {
        int P;
        cin >> P;
        P--;
        locs.push_back(P);
    }
    locs.push_back(N - 1);
    int tsum = 0;
    int tmax = 0;
    for (int j = 0; j + 1 < (int)locs.size(); j++) {
        int nless = 0;
        for (int i = locs[j]; i + 1 <= locs[j + 1]; i++) {
            if (A[i] != A[i + 1])
                nless++;
        }
        if (nless & 1)
            nless++;
        tsum += nless;
        tmax = max(tmax, nless);
    }
    int ans = max(tmax, tsum / 2);
    cout << ans << '\n';
}

int main() {
    ios_base::sync_with_stdio(false), cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--)
        solve();
}