题意
给定一个长度为 $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)$。