§ 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 |
|