← 返回题单
题单练习 树状数组
← 上一题 下一题 →

A6897 | 求和与替换

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

设 $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$ 和 $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 操作。

输出格式

对于每个 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
C++ 编辑器
输入
输出