Harbour.Space Scholarship Contest 2021-2022 (Div. 1 + Div. 2)
F. Pairwise Modulo
题意
给定长度为 $n$ 且互不相同序列 $A$，对每个 $k=1\sim n$ 计算
$$ f(k)=\sum_{i=1}^k\sum_{j=1}^k a_i\bmod a_j $$
题解
不难发现
$$ f(k)=f(k-1)+\sum_{i=1}^k a_i\bmod a_k+\sum_{i=1}^k a_k\bmod a_i\\ \sum_{i=1}^k a_i\bmod a_k=\sum_{i=1}^{k-1}a_i-\sum_{i=1}^{k-1}\lfloor \frac {a_i}{a_k}\rfloor a_k\\ \sum_{i=1}^k a_k\bmod a_i=(k-1)a_k-\sum_{i=1}^{k-1}\lfloor \frac {a_k}{a_i}\rfloor a_i\\ $$
对于 $\sum_{i=1}^{k-1}\lfloor \frac {a_i}{a_k}\rfloor a_k$，显然可以枚举 $d=\lfloor \frac {a_i}{a_k}\rfloor$ 的取值，然后根据区间 $[d\times a_k,(d+1)\times a_k)$ 中数值的个数计算贡献。
对于 $\sum_{i=1}^{k-1}\lfloor \frac {a_k}{a_i}\rfloor a_i$，一个暴力的想法是利用整数分块枚举 $d=\lfloor \frac {a_k}{a_i}\rfloor$，然后根据区间 $[d\times a_k,(d+1)\times a_k)$ 中数值的和计算贡献。
询问次数 $O(n\log n+n\sqrt v)$，于是总时间复杂度 $O\left(n\log^2 n+n\sqrt v\log2 v\right)$。非常卡常，据说能过，但我没过。
优化一
不难发现查询次数是 $O(n\sqrt v)$，更新次数是 $O(n)$。考虑利用分块构造 $O(1)$ 查询 $O(\sqrt v)$ 更新的数据结构。
具体的，$O(\sqrt v)$ 维护每个块内部的前缀和以及所有块的前缀和，即可支持 $O(1)$ 查询。总时间复杂度 $O(n\sqrt v)$。
优化二
对于 $\sum_{i=1}^{k-1}\lfloor \frac {a_k}{a_i}\rfloor a_i$，提前处理好 $a_i$ 对值域的贡献。
具体的，对 $[d\times a_i,(d+1)\times a_i)$，$a_i$ 的贡献为 $d\times a_i$。于是更新次数 $O(\log v)$，查询次数 $O(1)$，时间复杂度 $O(n\log^2 v)$。
