文章目录

CCPC 2021 CF Gym 103409 H Popcount Words 做题笔记

发布于

题意

有一个无限长的字符串 $s$,其中 $s_i = \operatorname{popcount}\left(i\right)$

给定 $n$ 个区间 $\left[l_i, r_i\right]$,令字符串 $S = s_{l_1\ldots r_1} + \cdots + s_{l_n\ldots r_n}$。

$q$ 次询问,每次查询一个 01 串 $t_i$ 在 $S$ 中的出现次数。

$1 \leq n, q \leq 10^5, 1 \leq l_i \leq r_i \leq 10^9, \sum \lvert T_i\rvert \leq 5 \times 10^5$

题解

如果 $S$ 长度很小,我们可以把所有 $t_i$ 建一个 AC 自动机,然后在上面跑 $S$。维护一个数组 $v$,每次跑到一个点 $x$,把 $v_x$ 加上 $1$。
$t_i$ 的答案即为 Fail 树上 $t_i$ 子树中 $v$ 的和。

注意到,建 AC 自动机和求答案是 $\Theta \left(\sum \lvert T_i\rvert\right)$ 的,但是在 AC 自动机上跑 $S$ 是 $\Theta \left(\lvert S \rvert\right)$ 的,无法接受,所以需要加速跑 $S$ 的过程。

接下来,我们看一看 $s$ 长什么样:
$\tt011010011001011010010110011010011$
我们可以使用如下递推式来生成 $s$:
初始时 $s = \tt0$,$s = s + s'$,其中 $s'$ 表示 $s$ 01 翻转后的字符串。
即每次把 $s$ 01 翻转后的字符串拼接到 $s$ 后面。

令 $T_k = s_{0 \ldots 2^k -1}$,即 $T_k$ 为 $s$ 的前 $2_k - 1$ 个字符组成的字符串。
这样,我们可以把 $S$ 拆成 $\Theta\left(\log \lvert S\rvert\right)$ 个区间,每个区间都是 $T_k$ 或者 ${T'}_k$。

举个例子,$\tt01011010010110$ 就可以拆成 $T_1 + T_2 + {T'}_3$。

同样的,我们也可以用递推的方式生成 $T_k$:$T_k = T_{k - 1} + {T'}_{k - 1}$

现在,$S$ 由 $\Theta\left(\lvert S\rvert \log \lvert S\rvert\right)$ 段 $T_k$ 拼接而成。

考虑使用如下方式快速跑 $T_k$:
设 $f\left(x, k, 0/1\right)$ 表示从 AC 自动机上的一点 $u$ 开始跑 $T_k/{T'}_k$,会跑到的点。
维护 $g\left(x, k, 0/1\right)$ 表示从 AC 自动机上的一点 $u$ 开始跑 $T_k/{T'}_k$,所有途经的点,的 $v$ 数组都加上 $1$。
即我们通过把 $g\left(x, k, 0/1\right)$ 加上 $1$,来代替 从 AC 自动机上的一点 $u$ 开始跑 $T_k/{T'}_k$,所有途经的点,的 $v$ 数组都加上 $1$。最后求答案的时候再还原回去。

接下来考虑快速求 $f\left(x, k, 0/1\right)$。
由于 $T_k = T_{k - 1} + {T'}_{k - 1}$,所以 $f\left(x, k, 0/1\right) = f\left(f\left(x, k - 1, 0/1\right), k - 1, 1/0\right)$,相当于先从 $x$ 开始跑一个 $T_{k - 1}$,又跑了一个 ${T'}_{k - 1}$。类似于倍增。

接下来就可以把 $f$ 处理出来,然后逐个枚举 $S$ 的每一段,然后先把 $g\left(x, k, 0/1\right)$ 加上 $1$,接着当前点 $x = f\left(x, k, 0/1\right)$。

这样 $S$ 就跑完了。
现在的问题是如何把 $g\left(x, k, 0/1\right)$ 还原到每一个点。

考虑到 $g\left(x, k, 0/1\right)$ 的贡献可以等价的推给 $g\left(\cdots, k - 1, 0/1\right)$,逐步推下去之后就可以全部推到 $g\left(\cdots, 0, 0/1\right)$ 上,就相当于是原来点的贡献了。

从 $\Theta \left(\log \lvert S \rvert\right)$ 到 $1$ 枚举 $k$,做:
$g\left(x, k - 1, 0/1\right) += g\left(x, k, 0/1\right)$
$g\left(f\left(x, k - 1, 0/1\right), k - 1, 1/0\right) += g\left(x, k, 0/1\right)$
$g\left(x, k, 0/1\right) = 0$

即可。


暂无评论

发表评论