F. Pairwise Modulo

给定一个长度为$n$的数组，定义函数$p_k$为：$\sum_{1<=i,j<=k}^{} a_i \ mod \ a_j$

请你求出$p_1,p_2,…,p_n$

数据范围：$n<=2e5,a_i<=3e5$

分析：

第$k$项$p_k$的值能由$p_{k-1}$递推得出，即$p_k=p_{k-1}+\sum_{1<=i<=k}^{} a_i \ mod \ a_k$

$p_k$的值可以分为两部分，第一部分是$a[k]$对$a[1,…k-1]$的数取模，第二部分是$a[1,…k-1]$对$a[k]$取模。

将$p_k$分为$s_k$和$t_k$两部分，即

$s_k=\sum_{i>j}a_i\ mod \ a_j$

$t_k=\sum_{i<j}a_i\ mod \ a_j$

$s_k$和$t_k$都可以递推求出，即$s_k=s_{k-1}+\sum_{i=1}^{k-1}(a_k\ mod\ a_i)=s_{k-1}+a_k*(k-1)-\sum_{i=1}^{k-1}(a_i·\left \lfloor \frac{a_k}{a_i} \right \rfloor )$

$t_k=t_{k-1}+\sum_{i=1}^{k-1}a_i\ mod\ a_k=t_{k-1}+\sum_{i=1}^{k-1}a_i-\sum_{i=1}^{k-1}(a_k·\left \lfloor \frac{a_i}{a_k} \right \rfloor )$

①求$s_k$：

问题的难点在于$\sum_{i=1}^{k-1}(a_i·\left \lfloor \frac{a_k}{a_i} \right \rfloor )$这个式子，不易直接求解，我们分别统计每个$a_i(i<k)$对$s_k$的贡献

对于所有在范围$[a_i,2a_i)$​​的$a_k$​​，贡献是$-a_i$​​

对于所有在范围$[2a_i,3a_i)$​​的$a_k$​​，贡献是$-2a_i$​​

…

对于所有范围$[d·a_i,(d+1)a_i)$​的$a_k$​，贡献是$-d·a_i$​

根据以上分析，用树状数组维护每个点所积累的贡献值，区间修改+单点查询，所以要维护贡献值的差分

②求$t_k$：

问题的难点在于$-\sum_{i=1}^{k-1}(a_k·\left \lfloor \frac{a_i}{a_k} \right \rfloor )$，

对于所有在范围$[a_k,2a_k)$​​​的$a_i$​​​，贡献是$-a_k$​​​

对于所有在范围$[2a_k,3a_k)$​​​的$a_i$​​​，贡献是$-2a_k$​​​

…

对于所有范围$[d·a_k,(d+1)a_k)$​​​的$a_i$​​​，贡献是$-d·a_k$

我们还需维护一个树状数组，统计$a_k$之前每个数的出现次数，然后在树状数组中求前缀和就能得到$[a,b]$这段区间的数出现多少次了

最后，$s_k$和$t_k$的值累加，就是当前的$p_k$值

#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;

const int N = 2e5 + 5, M = 3e5 + 5;
ll tr[M], tr1[M], a[N];

int n;

ll lowbit(int x)
{
    return x & -x;
}

void add(ll tr[], int x, ll c)  // 位置x加c
{
    for (int i = x; i < M; i += lowbit(i)) tr[i] += c;
}

void add1(ll tr[], int x, ll c)
{
    for(int i = x; i < M; i += lowbit(i)) tr[i] += c;
}
ll sum(ll tr[], int x)  // 返回前x个数的和
{
    ll res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}

signed main()
{
    scanf("%lld", &n);

    ll pre_sum = 0, ans = 0;
    for(int i = 1; i <= n; i ++ )
    {
        int x;
        scanf("%lld", &x);
        ans += x * (i - 1ll);//sk
        ans += pre_sum;//tk
        pre_sum += x;
        ans += sum(tr, x);
        for(int d = 1; d* x < M; d ++ )
        {
            int l = d * x, r = min(M, (d + 1)* x - 1);
            ans -= (sum(tr1, r) - sum(tr1, l - 1)) * d * x;
            add(tr, l, -d * x), add(tr, r + 1, d * x);
        }
        add1(tr1, x, 1);
        cout << ans << " ";
    }
    return 0;
}