A6897. 求和与替换
编程题
提高+/省选-
知识点
题目描述
设 $D(x)$ 表示正整数 $x$ 的正约数个数。例如，$D(2)=2$（$2$ 能被 $1$ 和 $2$ 整除），$D(6)=4$（$6$ 能被 $1$、$2$、$3$ 和 $6$ 整除）。
给定一个包含 $n$ 个整数的数组 $a$。你需要处理两种类型的操作：
1. REPLACE $l$ $r$：对于每一个 $l\le i\le r$，将 $a_i$ 替换为 $D(a_i)$；
2. SUM $l$ $r$：计算 $\sum_{i=l}^{r} a_i$。
每次 SUM 操作需要输出结果。
给定一个包含 $n$ 个整数的数组 $a$。你需要处理两种类型的操作：
1. REPLACE $l$ $r$：对于每一个 $l\le i\le r$，将 $a_i$ 替换为 $D(a_i)$；
2. SUM $l$ $r$：计算 $\sum_{i=l}^{r} a_i$。
每次 SUM 操作需要输出结果。
输入格式
第一行包含两个整数 $n$ 和 $m$（$1\le n,m\le 3\cdot 10^5$）。
第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$1\le a_i\le 10^6$）。
接下来 $m$ 行，每行包含 $3$ 个整数 $t_i,l_i,r_i$：
- 若 $t_i=1$，表示 REPLACE $l_i$ $r_i$
- 否则表示 SUM $l_i$ $r_i$
保证至少有一次 SUM 操作。
第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$1\le a_i\le 10^6$）。
接下来 $m$ 行，每行包含 $3$ 个整数 $t_i,l_i,r_i$：
- 若 $t_i=1$，表示 REPLACE $l_i$ $r_i$
- 否则表示 SUM $l_i$ $r_i$
保证至少有一次 SUM 操作。
输出格式
对于每个 SUM 操作，输出一行结果。
输入输出样例
输入 #1
7 6 6 4 1 10 3 2 4 2 1 7 2 4 5 1 3 5 2 4 4 1 5 7 2 1 7
输出 #1
30 13 4 22
说明/提示
## 样例解释
- 第一次 SUM：$6+4+1+10+3+2+4=30$
- 第二次 SUM：$10+3=13$
- 执行一次 REPLACE(3,5) 后：把 $a_3,a_4,a_5$ 替换成它们的约数个数
- 后面同理，按操作顺序计算即可
- 第一次 SUM：$6+4+1+10+3+2+4=30$
- 第二次 SUM：$10+3=13$
- 执行一次 REPLACE(3,5) 后：把 $a_3,a_4,a_5$ 替换成它们的约数个数
- 后面同理，按操作顺序计算即可