题目描述

给一个长度为 $n$ 的 01 序列，一个整数 $k$，并进行 $m$ 次询问。每次询问给出一个区间，可以进行若干次操作：每次选择这个区间的长度为 $k$ 的子区间，将子区间的每一位取反 —— 至少需要几次操作才能将这个区间内的所有元素变成 $0$？

思路

$\small O(nmk)$

不妨从最简单的暴力开始想起：从左往右数的第一个 $1$（不管是原来就有的还是新产生的）一定是一个要反转的子区间的左端点 —— 这是因为如果将它忽略，以它右边的数为左端点的反转子区间再也无法改变这个 $1$。于是对于每次操作，我们可以从左往右枚举，遇到一个 $1$ 就以它为左端点暴力做一次取反。

$\small O(nm)$

当我们求出区间的差分序列，一次子区间的取反其实就是在差分序列上对要取反子区间的左右端点处进行了取反。最后只需要让差分序列全是 $0$ 就可以了。对于以 $i$ 位置为左端点的，长度为 $k$ 的子区间，改变的其实就是差分序列上 $i$ 位置和 $i+k$ 位置的 $1$。从左往右扫一遍，遇到一个 $1$ 就做一次这样的操作。

$\small O(n+m)$

在上面的差分优化上进一步思考：对于每个位置 $i$，如果 $i \mod k $ 的值相同，那它们就是相互联系的，否则就是相互独立的。我们可以通过若干次操作将相互联系的位置抵消掉，而相互独立的位置则不能相互抵消。手玩几组数据可以很深刻地体会这一点，在这里不妨看一下这个样例：原序列是 0100011010，我们可以得到其差分序列为 0110010110。当 $k=2$ 时我们可以将差分序列上 $1$ 的位置分为两类：$\mod k$ 为 $0$ 的和 $\mod k$ 为 $1$ 的。具体来讲：

%k == 0: 2, 6, 8, 10
%k == 1: 3, 9

拿位置 3 和 9 来说，虽然它们之间的距离不等于 $k$，即这两个位置的 1 不能通过一次操作全变成 0，但是因为它们对 $k$ 取模的结果相同，我们可以将 3 位置变成 0，将 5 位置变成 1，将 5 位置变成 0，将 7 位置变成 1，将 7 位置变成 0，将 9 位置变成 0。这样可以看作是消耗 3 次将 3 位置和 9 位置同时变成 0。如果是不同的种类，即相互独立的位置，例如位置 3 和位置 6，就不能通过这种方法一起变成 0，反而会产生新的 1。

可以想到，只有询问区间里每种位置的个数都是偶数的时候才有的解，否当同类两两配对抵消之后，一定会剩下若干个种类两两不同的位置 —— 这些位置不能通过上面说的方法抵消，所以一定会产生新的 1，于是我们永远也无法将差分序列变成全是 0，询问误无解。

使用哈希判断当前的区间里面每一类位置的个数是奇数还是偶数：给同一类的差分序列上为 1 的位置赋一个同一个的随机值，用哈希值去异或它，这样当同一类位置个数为偶数时，异或下来的值就是 0。

最小操作次数计算也很简单：同一类位置两两抵消时，所消产生操作次数只与位置的差值，即它们的距离的有关。贪心地选择相距最近的位置两两抵消，可以得到最小的次数要求。例如在上面的例子中第一类的四个位置 2，6，8，10：如果 2 和 6，8 和 10 抵消，需要进行三次 3 次操作，这个次数是最少的，可以手玩几个样例感受一下。维护这样求出的总消耗的前缀和，每一类从右往左第奇数个产生正贡献，第偶数个产生负贡献（因为是右面的减去左面的），当从左往右扫，右边出现同一类新的位置时，从右往左数的奇偶性会改变，正负也会交换，所以当出现这样的新位置时，直接将同类位置的贡献取反在和新位置的贡献一起加入前缀即可。、

虽然我们将原序列取反问题转化成了差分序列上的问题，但是每一次的询问目标都是原序列的一段区间，差分必然会受到询问区间之外的位置的影响。例如询问区间是 $[l,r]$, 那么我们需要「强制」使得原序列 $l-1$ 和 $r+1$ 的位置是 0。否则我们看上去把差分序列的区间都变成了 0，实际上却是把原序列都变成 1 了。具体来讲，如果原序列 $l$ 位置是 1，那么即使差分是 0 也要做一次取反操作；如果原序列 $r$ 位置是 1，那么即使差分是 1 也不需要取反操作。

细节非常多，写起来比较麻烦 —— 而且一定要记得位运算加括号！

Code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<climits>
#include<utility>
#define int long long
using namespace std;
const int MaxN = 2000006;
int n, m, k, hashval[MaxN], sum[MaxN], last[MaxN], group[MaxN], password[MaxN], pre[MaxN];
bool ori[MaxN], dif[MaxN];
inline int Read(){
	int num = 0, op = 1;
	char ch = getchar();
	while(!isdigit(ch)){
		if(ch == '-') op = -1;
		ch = getchar();
	}
	while(isdigit(ch)){
		num = num * 10 + ch - '0';
		ch = getchar();
	}
	return num * op;
}

signed main(){
	n = Read(), k = Read(), m = Read();
	srand(20040131);
	for(int i=0; i<k; i++)
		password[i] = ((long long)rand()*rand()*rand());
	ori[0] = 0;
	for(int i=1; i<=n+1; i++){
		if(i<=n) scanf("%1d", &ori[i]);
		dif[i] = ori[i] ^ ori[i-1];
		sum[i] = sum[i-1];
		hashval[i] = hashval[i-1];
		group[i] = last[i%k];
		if(dif[i]){
			sum[i] += (-last[i%k] + (i+k-1)/k) - last[i%k];
			last[i%k] = -last[i%k] + (i+k-1)/k;
			hashval[i] ^= password[i%k];
		}
		pre[i] = last[i%k];
	}
	for(int i=1; i<=m; i++){
		int l = Read(), r = Read();
		int lkey = ori[l]?password[l%k]:0, rkey = ori[r]?password[(r+1)%k]:0;
		if((hashval[r] ^ rkey ^ lkey) != hashval[l]){
			printf("-1\n");
			continue;
		}
		int ans = sum[r] - sum[l];
		if(ori[r]) ans += (-group[r+1] + (r+k)/k) - group[r+1];
		if(ori[l]) ans -= (-pre[l] + (l-1+k)/k) - pre[l];
		if(ans < 0) ans = -ans;
		printf("%lld\n", ans);
	}
	return 0;
}