Sol
设 $s(a,b,c,d) = \sum_{i=a}^b \sum_{j=c}^d [ a_i \mid a_j ] + [ a_j \mid a_i ]$
考虑莫队，相当于将原问题转化成了 $O(n)$ 次形如 $\sum_{i=r+1}^{r’} s(l,i-1,i,i)$ 或 $\sum_{i=l’}^{l-1} s(i+1,r,i,i)$ 的询问（分别对应了左端点和右端点的移动）。
差分一下得到：
这样我们就把原问题转化成了 $O(n)$ 个形如 $\sum_{i=l}^r s(1,p,i,i)$ 的询问，并且 $\sum r-l = O(n\sqrt n)$。
考虑扫描线，那么我们要支持的操作就是：
- 加入一个数
- 给出一个区间，枚举这个区间中的每一个数 $x$ ，查询已经加入的数中
1) 有多少个数是 $x$ 的倍数
2) 有多少个数是 $x$ 的因数
对于第一问：每加入一个数，我们就枚举它所有的约数、打上标记，查询的时候直接返回 $x$ 的标记即可。
对于第二问：我们考虑对加入的数进行根号分治。对于超过 $\sqrt n$ 的数，直接枚举它所有的倍数打上标记；对于小于等于 $\sqrt n$ 的数，我们枚举所有的 $y\in [1,\sqrt n]$ ，然后处理出序列的每个前缀中有多少个数是 $y$ 的倍数（以支持查询一个区间内有多少个数是 $y$ 的倍数），扫描线的时候维护前 $p$ 个位置有多少个数等于 $y$ 即可。
总时间复杂度 $O(n\sqrt n)$ ，空间复杂度 $O(n)$ 。