文章目录

还是一道自己出的题

发布于

题意

给定一个长度为 $n$ 的数组 $a$。有 $q$ 个询问,每次询问给出 $a, b, m, r$,求在范围 $\left[a, b\right]$ 中,$a_i \bmod m = r$ 的个数。强制在线。

$1 \leq n, q \leq 3 \times 10^5, 1 \leq a_i, m \leq n, 0 \leq r < m$

也可以想一下离线的做法。

题解

首先对值域根号分治。对于 $m$ 小于等于 $\sqrt n$ 的询问,直接开桶维护。
对于 $m$ 大于 $\sqrt n$ 的询问,考虑如下做法。
分块。对于每个块,维护当前块中每个值出现的次数。然后对块前缀和。
对于每个询问,先 $\Theta \left(\sqrt n\right)$ 求出当前区间中每个数的出现次数,存储在一个数组 $c$ 中。然后,枚举所有模 $m$ 余 $r$ 的数 $x$(每次 $r$ 加上 $m$,知道超过 $10000$),直接在数组 $c$ 中查 $x$ 的出现次数。耗时 $\mathcal O\left(\sqrt n\right)$,统计总和。

总复杂度 $\mathcal O\left(n + q \sqrt n\right)$。


暂无评论

发表评论