题解

思路

对任意素数 $p$，一对高度的最大公约数中 $p$ 的指数是两数 $p$ 进指数的较小值。把“较小值”按阈值展开，就能把成对 gcd 的乘积转化为区间内可动态维护的整除计数。

做法

设 $c_{p^t}$ 表示当前区间中能被素数幂 $p^t$ 整除的高度个数。所有成对 gcd 乘积中素数 $p$ 的总指数为

这是因为一对数对指数的最小值至少为 $t$，当且仅当两数都能被 $p^t$ 整除。

小规模可以直接枚举所有数对。全相等时，长度为 $L$ 的区间答案是 $h^{\binom L2}$；只有一个询问时可顺次加入区间元素。对于 $n,q\le5000$，每个询问重新扫描区间并维护所有素数幂计数。

满分做法使用莫队。加入高度 $x$ 时，对 $x$ 的每个素数幂因子 $p^t$，设加入前计数为 $c$，新产生的数对为当前 $c$ 个同样能被 $p^t$ 整除的元素，因此答案乘以 $p^c$，随后计数加一。删除时先将计数减一，再乘以 $p^{-c}$。预先按每个实际出现的素因子建立正幂和逆幂表，即可让一次阈值更新为 $O(1)$。

正确性证明

阈值恒等式证明了每个素数在答案中的指数。莫队加入操作恰好把新元素与区间内已有元素组成的所有新数对贡献加入答案；删除操作精确除去被删除元素与剩余元素组成的贡献。区间移动后维护值因此始终等于该区间所有成对 gcd 的乘积，莫队重排询问不改变对应区间，故所有输出正确。

复杂度

每个 $h_i\le10^5$ 只含 $O(\log h_i)$ 个素数幂阈值。满分算法的莫队移动次数为 $O((n+q)\sqrt n)$，每次移动再乘以该元素的素数幂阈值数；空间复杂度为 $O(n+q+V)$，其中 $V=10^5$。