【CodeM初赛A 5】数列互质 题解

题目大意

  给出一个长度为 $n$ 的序列 $a_1...a_n$，有 $m$ 个询问，每次询问给出 $l, r, k$，问 $a_l...a_r$ 中，有多少数的出现次数与 $k$ 互质。
  $n, m \leq 5e4，1 \leq a_i, k \leq n$
  时限 6s

题解

  区间问题可以考虑莫队，可以维护一个桶 $t_i$ 表示有多少数的出现次数是 $i$。

  但是统计答案不方便，要把整个桶扫一次。

  于是设个阈值 $s=\sqrt n$。如果某个数在全局的出现次数 $>s$，就提取出来单独对每个询问做贡献，剩下的数就做莫队。