记 $c_i=\gcd(i,a_i)$，操作二实际上就是给定初始的 $x$，每次令 $x\to c_x+x$，问跳出序列的路径上所有 $a_x$ 之和。

这个形式非常像 [HNOI 2010] 弹飞绵羊 这道题，实际上可以直接照搬分块做法，先将序列分块。

设 $f_i$ 表示从 $i$ 出发跳出快后到达那个位置，$g_i$ 表示从 $i$ 跳到 $f_i$ 的路径权值和。

假设 $i$ 所在的块的右边界为 $r$，则分情况。

1. 若 $i+c_i>r$：$f_i=i+c_i,g_i=a_i+w_i$。

2. 若 $i+c_i\le r$：$f_i=f_{i+c_i},g_i=a_i+g_{i+c_i}$。

注意单点修改整个块都要重构，所以单点修改的复杂度为 $O(B)$。

回到本题，查询的复杂度是显然的 $O\left(\frac{n}{B}\right)$，考虑如何修改。

不难发现，$c_i$ 在修改过程中只会不断增大趋近于 $i$，每次增大都会乘上一个数，均摊分析可以知道所有 $c_i$ 的变化次数不超过 $1\sim n$ 的质因子个数之和，即 $n\log n$。

所以每次要找到哪个数要单点修改后，直接暴力重构块即可，然后用分块维护区间 $a_i\gets a_i\times c$ 的操作。这一部分的复杂度为 $O(nB\log n)$。

问题在于，如何快速找到哪个数要单点修改，记 $b_i=\frac{i}{c_i}$。我最初的做法是每个块记录这个块 $u$ 所有 $b_i$ 每个具体质因子 $x$ 的和记为 $p_{u,x}$，修改时，先将 $c$ 拆成 $\log n$ 个区间乘质因子的操作，对于第 $i$ 个块乘质因子 $x$，则判断 $p_{i,x}$ 取值，若大于 $0$，则暴力修改块，反之则跳过。

最终的时间复杂度为 $O\left(nB\log n+\frac{n^2}{B}\log V\right)$，空间复杂度为 $O(nB)$，大概取 $B=500$ 左右最快，只能在 LOJ 通过，常数太大了。

其实有一种更简单的区间找数操作，对于质数 $x$ 单独开一个 set，若 $b_i$ 有 $x$ 为质因子，则在 set 中插入 $i$。每次修改 $[l,r]$，直接暴力找 $[l,r]$ 里所有的数，每个数只修改 $c_i,b_i$，最后将有单点修改操作的块重构，注意维护此时的 set。

这样此时找数的时间复杂度也是可以均摊的，时间复杂度为 $O\left(nB\log n+\frac{n^2}{B}+n\log^2n\right)$，此时 $B=\sqrt{\frac{n}{\log n}}$ 最优，大概在 $n=200\sim 300$ 的时候跑的比较快，且空间复杂度为 $O(n)$。已经可以通过 COGS 的测试了。

官方题解。来源：清华大学学生算法协会仓库

题目简述

给定正整数 $n$ 和长为 $n$ 的正整数序列 $a$。对于正整数 $x$，定义$\newcommand{dfrac}[2]{\displaystyle\frac{#1}{#2}}$

$$f(x)=\begin{cases}0&(x>n)\\f(x+\gcd(x,a_x))+a_x&(x\leq n)\end{cases}$$

现有 $q$ 次操作，分为两类：

• 1 l r c：将所有满足 $l\leq i\leq r$ 的 $a_i$ 的值乘以 $c$。
• 2 x：查询 $f(x)$ 对 $998244353$ 取模的值。

做法解析

做法的核心是分块。将序列分为长度为 $B$ 的一些块，并维护块内每个位置不断向后跳时第一次跳出块时对应的位置和这个过程中 $a_x$ 的总和，则可以 $O\left(\dfrac{n}{B}\right)$ 的处理一次查询。修改虽然是区间修改，但维护新的跳到的位置时，$\gcd(x,a_x)$ 的改变次数最多是 $x$ 质因子分解后对应幂次的总和，可以说明总的改变次数是 $O(n\log\log n)$ 的，因此可以用 set 对每个质数维护还可能被修改的位置，每次修改时暴力重构整个块；而对于维护一路上的权值和，可以对整块的修改打标记、散块的修改直接暴力，复杂度为 $O\left(B+\dfrac{n}{B}\right)$。因此总的复杂度大致为 $O\left(q\left(B+\dfrac{n}{B}\right)+n\log\log n\cdot (B+\log n)\right)$，综合分析常数和理论结果，大致取 $B=300$ （差不多是 $\dfrac{n}{\sqrt3}$）时最优。

时限给了 $4\text{s}$，实际上 std 取 $B=300$ 需要跑大约 $1.3\text{s}$，取 $B=500$ 也只需要大约 $2\text{s}$，所以应该是完全不卡常的。