[EZOI][1225NOI模拟赛]operation(差分+前缀和+hash)

发表于 | 评论数：

§ 1 题意

给出一个长度为 $n$ 的 $01$ 序列以及一个正整数 $k$，有 $m$ 次询问，每次给出一个区间 $[l,r]$，你可以进行若干次操作，每次选择 $[l,r]$ 的一个长度为 $k$ 的子区间，将子区间上的所有元素取反，询问至少需要多少次操作才能将 $[l,r]$ 内所有元素变成 $0​$。

注意每次询问独立，在一个询问中进行的操作不会影响另一个询问。

$k\leq n\leq 2\times 10^6,\ \ m\leq 5\times 10^5$。

§ 2 分析

考虑将原数组差分，记差分数组为 $d$（代码中没有储存差分数组）。

容易发现，将原数组 $[i,i+k-1]$ 上的元素取反，相当于将 $d_i$ 和 $d_{i+k}$ 取反。

若此时 $d_i$ 和 $d_{i+k}$ 均为 $1$，则我们可以视为两者同时消掉。

进一步发现，在 $d$ 数组中，${\rm mod}\ k$ 不相等的下标相互独立，可以分开考虑。

对于 $d$ 数组中下标 ${\rm mod}\ k$ 相等的 $1$，显然将相邻两个 $1$ 消掉操作数最少。

然而题目中 $k$ 的范围过大，若按 ${\rm mod}\ k$ 分组处理后合并，则复杂度与暴力同阶。

首先考虑如何快速判断无解情况。以下分析均忽略边界情况。

我们考虑 ${\rm hash}$，对每一组随机加权，用 ${\rm rnd}_i\ (0\leq i\lt k)$ 表示 ${\rm mod}\ k=i$ 的组的权值。

考虑到区间 $[l,r]$ 无解当且仅当 $[l,r]$ 中有奇数个下标 ${\rm mod}\ k$ 相同的 $1$。

维护前缀异或和 ${\rm xs}_n=\bigoplus\limits_{i=1}^n{\rm rnd}_i$，若 ${\rm xs}_r\oplus{\rm xs}_l\neq 0$ 则一定无解。

然后考虑如何快速计算答案。

考虑到每一组的 $1$ 的贡献正负交替，将前缀和计算式的符号改为 $-$ 即可。

最后注意边界处理下标 $l$ 和 $r+1$，防止将数组化为全 $1$ 而非全 $0$。

总时间复杂度为 $O(n+k+m)$。

§ 3 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#define MAXN 2000005
using namespace std;
typedef long long ll;

inline void getint(int &num){
	register int ch, neg = 0;
	while(!isdigit(ch = getchar())) if(ch == '-') neg = 1;
	num = ch & 15;
	while(isdigit(ch = getchar())) num = num * 10 + (ch & 15);
	if(neg) num = -num;
}

int n, k, m, rnd[MAXN], xs[MAXN], f[MAXN], a[MAXN], b[MAXN], c[MAXN];
char s[MAXN];

int main(){
	srand(19260817), getint(n), getint(k), getint(m), scanf("%s", s + 1), s[0] = '0';
	for(register int i = 0; i < k; i++) rnd[i] = ((ll)rand() << 15) ^ rand();
	for(register int i = 2; i <= n; i++){
		xs[i] = xs[i - 1], f[i] = f[i - 1];
		if(s[i] != s[i - 1]) xs[i] ^= rnd[i % k], f[i] += i - (a[i % k] << 1), a[i % k] = i - a[i % k];
		b[i] = a[i % k], c[i] = a[(i + 1) % k];  // 边界处理时使用
	}
	while(m--){
		int l, r; getint(l), getint(r);
		int nosol = xs[l] ^ xs[r], ans = f[r] - f[l];
		if(s[l] == '1') nosol ^= rnd[l % k], ans -= l - (b[l] << 1);
		if(s[r] == '1') nosol ^= rnd[(r + 1) % k], ans += r + 1 - (c[r] << 1);
		printf("%d\n", nosol ? -1 : ans / k);
	}
	return 0;
}