P15251 [NOSOI R1] Free Pairs

> 这很自由，包括有序对

若一个正整数不被任何大于 $1$ 的平方数整除，则称其为自由的。例如，$1$、$2$、$3$、$5$、$6$、$7$ 是自由的，而 $4$、$8$、$9$、$12$ 不是。 给定一个长度为 $n$ 的正整数序列 $a_1, a_2, \dots, a_n$，你需要处理 $m$ 次操作。操作有两种类型： * 修改：给定下标 $i$ 和值 $x$，将 $a_i$ 修改为 $x$。 * 查询：给定区间 $[l, r]$，求满足 $l \le i \le j \le r$ 且 $\gcd(a_i, a_j)$ 是自由的有序对 $(i, j)$ 的个数。 **请注意，有序对 $(i, j)$ 包括 $i = j$ 的情况。**

第一行包含两个整数 $n, m$，表示序列长度和操作次数。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示初始序列。 接下来 $m$ 行，每行描述一个操作： * 修改操作以字符 `U` 开头，后接两个整数 $i$ 和 $x$，表示将 $a_i$ 修改为 $x$。 * 查询操作以字符 `Q` 开头，后接两个整数 $l$ 和 $r$，表示查询区间 $[l, r]$。

对于每个查询操作，输出一行一个整数，表示满足条件的有序对个数。

#### **样例解释** 初始序列为 $[1, 2, 4]$。 第一个查询：区间 $[1, 3]$ 内有序对如下： $(1,1)$：$\gcd(1,1)=1$，无平方因子，满足。 $(1,2)$：$\gcd(1,2)=1$，满足。 $(1,3)$：$\gcd(1,4)=1$，满足。 $(2,2)$：$\gcd(2,2)=2$，无平方因子，满足。 $(2,3)$：$\gcd(2,4)=2$，满足。 $(3,3)$：$\gcd(4,4)=4$，有平方因子 $4$，不满足。 因此满足条件的有序对共有 $5$ 个。 修改后序列为 $[1, 2, 2]$。 第二个查询：区间 $[1, 3]$ 内所有有序对均满足条件，有序对共 $6$ 个，故输出 $6$。 #### 数据范围 **本题采用捆绑测试。** |$\text{sid}$|$pts$|$n$|$V$|$m$|特殊性质| |--|--|--|--|--|:--:| |$1$|$10$|$\leq 10$|$\leq 10^4$|$=2$|无| |$2$|$10$|$\leq100$|$\leq10^4$|$\leq 100$|无| |$3$|$10$|$\leq 750$|$\leq 10^4$|$\leq 500$|无| |$4$|$10$|$\leq 5\times 10^3$|$\leq 10^4$|$\leq 5\times 10^3$|$A$| |$5$|$10$|$\leq6\times10^4$|$\leq 10^4$|$\leq6\times 10^4$|$A$| |$6$|$10$|$\leq6\times10^4$|$\leq 10^4$|$\leq6\times 10^4$|$B$| |$7$|$20$|$\leq1\times 10^5$|$\leq 10^3$|$\leq1\times 10^5$|$C$| |$8$|$20$|$\leq 3\times10^5$|$\leq 10^4$|$\leq 3\times10^5$|无| 其中 $V=\max\{x,a_i\}$。 特殊性质 $A$：对于所有 $a_i,x$，保证数据在一定范围内随机生成。 特殊性质 $B$：对于所有查询操作 $l,r$，都有 $l=1,r=n$。 特殊性质 $C$：没有修改操作。 对于所有测试数据，$1 \le n, m \le 3\times 10^5$，$1 \le a_i,x \le 10^4$。