CF920F SUM and REPLACE

设 $D(x)$ 表示正整数 $x$ 的正约数个数。例如，$D(2)=2$（$2$ 能被 $1$ 和 $2$ 整除），$D(6)=4$（$6$ 能被 $1$、$2$、$3$ 和 $6$ 整除）。 给定一个包含 $n$ 个整数的数组 $a$。你需要处理两种类型的操作： 1. REPLACE $l$ $r$ —— 对于每一个 $l \leq i \leq r$，将 $a_i$ 替换为 $D(a_i)$； 2. SUM $l$ $r$ —— 计算 $\sum_{i=l}^{r} a_i$。 每次 SUM 操作需要输出结果。

第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 3 \cdot 10^{5}$）—— 数组的元素个数和要处理的操作数量。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 10^{6}$）。 接下来 $m$ 行，每行包含 $3$ 个整数 $t_i$、$l_i$、$r_i$，表示第 $i$ 个操作。如果 $t_i=1$，则该操作为 REPLACE $l_i$ $r_i$，否则为 SUM $l_i$ $r_i$（$1 \leq t_i \leq 2$，$1 \leq l_i \leq r_i \leq n$）。 保证至少有一次 SUM 操作。

对于每个 SUM 操作，输出一行结果。

由 ChatGPT 5 翻译