题意
今有一 01 串。现 \(q\) 次独立地询问，对于一个子串：
- 一次操作可以把其一个长为 \(k\) 的子串取反，问多少次操作可以将这个串清零（无法清零输出
-1）。
\(n\leq 2\times 10^6\)，\(q\leq 5\times 10^5\)。
题解
先异或差分，把位置按照 \(\bmod k\) 的结果分类，每一类都会有很多个为 \(1\) 的位置，这些为 \(1\) 的位置必须两两配对消掉。
于是给每个为 \(1\) 的位置按 \(\bmod 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\n",(pre[r]-pre[l]+a[l]*(2*ll[l]-l)+a[r]*(r+1-2*rr[r]))/k);
}
return 0;
}