[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;
}