【题解】LOJ#6500. 「雅礼集训 2018 Day2」操作 / tiramisu【20201030 CSP 模拟赛】

题目链接

题目链接

题意

今有一 01 串。现 (q) 次独立地询问，对于一个子串：

• 一次操作可以把其一个长为 (k) 的子串取反，问多少次操作可以将这个串清零（无法清零输出 -1）。

(nleq 2 imes 10^6)，(qleq 5 imes 10^5)。

题解

先异或差分，把位置按照 (mod k) 的结果分类，每一类都会有很多个为 (1) 的位置，这些为 (1) 的位置必须两两配对消掉。

于是给每个为 (1) 的位置按 (mod k) 的结果分配一个随机的值，异或和为零就代表着所有 (1) 都配对了。所有为 (1) 的位置的贡献是一正一负的。注意边界上的值为 (1) 的情况。

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
const int N=2e6+10;
int Rand(){
	return rand()^(rand()<<15)^23333333;
}
int a[N],hsh[N],sd[N],pre[N],c[N];
int ll[N],rr[N];
int main(){
	int n,k,m;
	scanf("%d%d%d",&n,&k,&m);
	for(int i=1;i<=n;i++)scanf("%1d",a+i);
	for(int i=0;i<k;i++)sd[i]=Rand();
	for(int i=1;i<=n;i++){
		pre[i]=pre[i-1]; hsh[i]=hsh[i-1];
		if(a[i]^a[i-1]){
			hsh[i]^=sd[i%k];
			pre[i]+=i-2*c[i%k];
			c[i%k]=i-c[i%k];
		}
		ll[i]=c[i%k];
		rr[i]=c[(i+1)%k];
	}
	while(m--){
		int l,r;
		scanf("%d%d",&l,&r);
		if(hsh[l]^hsh[r]^(a[l]*sd[l%k])^(a[r]*sd[(r+1)%k]))puts("-1");
		else printf("%d
",(pre[r]-pre[l]+a[l]*(2*ll[l]-l)+a[r]*(r+1-2*rr[r]))/k);
	}
	return 0;
}