CF2217D Flip the Bit (Hard Version) Solution

链接

赛时犯唐，划分区间时记录的区间个数为 $k$，而不是 $k+1$ 直接掉了 48 rating。

# 题解

我们发现，对于翻转区间 $(l,r)$ 我们发现当 $(l,r)$ 中的数的颜色是相同的时候一定最优（对于不同的，总存在方案使其变为相同的，正确性显然），这样我们就可以考虑按照 $p_i$ 所在的位置划分为 $k+1$ 个区间。

第一个区间为 $i$ 到 $p_1$，第二个为 $p_1+1$ 到 $p_2$ 依此类推最后一个区间为 $p_k+1$ 到 $n$。

我们考虑在每个区间内部解决问题。

显然的是，对于每一个区间，如果说 $a_i \not = a_{i-1}$ 那这里是肯定需要划分的，我们可以考虑记录每个区间所需划分的位置的总数（记为 $P$）, 如果说一个区间内部的需要划分位置的个数已经比总的两两匹配的数量多了（当然这种情况只会出现一次，这里记为 $mx$），那其余的边界需要单独解决（最小次数为 $P - mx$），而这个点内部处理的次数为 $2 \times mx - P$ 加起来答案就是 $mx$，所以答案即是 $mx$ 和 $\frac {P} {2}$ 的最大值。

# Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cstring>
#ifdef _WIN32
#define getchar _getchar_nolock
#define putchar _putchar_nolock
#else
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif
#define pll pair<ll,ll>
#define pld pair<ld,ld>
typedef long long ll;
typedef long double ld;
typedef __int128 i128;
namespace io {
    using namespace std;
    template <typename T> void debug (T x) {
        cerr<<x<<'\n';
    }
    template <typename T> void debuglen (T x) {
        cerr<<x<<' ';
    }
    template <typename T,typename...Args> void debug (T x,Args...args) {
        cerr<<x<<' ';
        debug(args...);
    }
    template <typename T> void debug (T*lt,T*rt) {
        ll len=rt-lt;
        for (ll i=0;i<len;i++) {
            debuglen(*(lt+i));
        }
        cerr<<'\n';
    }
    inline ll read () {
        char x=getchar();
        ll ans=0,f=1;
        while (x<'0'||x>'9') {
            if (x=='-') {
                f=-1;
            }
            x=getchar();
        }
        while (x>='0'&&x<='9') {
            ans=(ans<<1)+(ans<<3);
            ans+=(x^'0');
            x=getchar();
        }
        return ans*f;
    }
    void print (ll x) {
        if (x<0) {
            x=-x;
            putchar('-');
        }
        if (x>=10) {
            print(x/10);
        }
        putchar(x%10+'0');
    }
}
using namespace io;
const ll N=2e5+5,mod=1e9+7,inf=2e18;
const ld eps=1e-6;
ll n,k,a[N],b[N],num[N];
inline void solve () {
	n=read(),k=read();
	for (ll i=1;i<=n;i++) {
		a[i]=read();
	}
	for (ll i=1;i<=k;i++) {
		b[i]=read();
		num[i]=0;
	}
	num[k+1]=0; 
	ll x=a[b[1]],tot=0,cnt=0,lt=0;
	for (ll i=1;i<=n+1;i++) {
		while (cnt<=k&&b[cnt]<i) {
			cnt++;
		}
		ll pl=i>n?0:x^a[i];
		if (pl!=lt) {
			tot++;
			num[cnt]++;
		}
		lt=pl;
	}
	tot++;
	tot>>=1;
	for (ll i=1;i<=k+1;i++) {
		tot=max(tot,num[i]);
	}
	print(tot);
	puts("");
}
int main () {
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
    ll T=1;
	T=read();
    while (T--) {
        solve();
    }
    return 0;
}