解题思路

题目要求支持两种操作：询问给定整数 $k$ 时，序列中有多少个数能被 $k$ 整除；以及单点修改某个位置的值。序列长度和操作次数均可达到 $2 \times 10^5$，每次询问都扫描整个序列会超时。

关键观察：一个数能否被 $k$ 整除，只与它的因子有关。我们可以把问题转化为维护每个除数对应的倍数个数：

• 维护数组 cntMul[d]：表示当前序列中能被 $d$ 整除的元素个数。
• 对于询问操作 1 k，直接输出 cntMul[k]，时间复杂度 $O(1)$。
• 对于更新操作 2 i x，设旧的值为 old，新的值为 x。我们需要将 old 的所有因子 $d$ 在 cntMul[d] 中减 $1$，再将 x 的所有因子 $d$ 在 cntMul[d] 中加 $1$，最后将序列中下标 $i$ 的元素更新为 $x$。
• 为了快速获得一个数的所有因子，使用类似筛法预先处理出 $1$ 到 $MAXA$（题目数值上限 $2\times 10^5$）每个数的所有因子，存储在 divisors 数组中。预处理复杂度约为 $O(MAXA \log MAXA)$。