我自己算的是 $O(n\sqrt n + n\ln n)$

但是程序跑的很慢，应该是复杂度算错了，有没有人能帮算一下

注意：保证 a 数组互不相同 且 $a[i]\leq3\times 10^5$

#include<bits/stdc++.h>

using namespace std;

#define int long long
#define INF 1ll<<30
#define lowbit(x) (x&(-x))
#define gb(x) ((x-1)/T + 1)

template<typename _T>
inline void read(_T &x)
{
	x=0;char s=getchar();int f=1;
	while(s<'0'||s>'9') {f=1;if(s=='-')f=-1;s=getchar();}
	while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+s-'0';s=getchar();}
	x*=f;
}

const int np =3e5 + 5;
const int cp = sqrt(np) + 10;
int maxn =0;
int a[np],T;
int pk[np];
int l_[cp],r_[cp];

struct val_Block{
	int sum[cp];
	int sum_[np];	
	inline void Init()
	{
		memset(l_,0x3f,sizeof(l_));
		for(int i=1;i<=3e5;i++)
		{
//			(!l_[gb(i)])? l_[gb(i)] = i:
			l_[gb(i)] = min(i,l_[gb(i)]);
			r_[gb(i)] = max(i,r_[gb(i)]);
		}
	}
	
	inline void upd(int x,int vl)
	{
		for(int i=x;i<=r_[gb(x)];i++) sum_[i] += vl;
		for(int i=gb(x);i<=gb(3e5);i++) sum[i] += vl;// vl;
	}
	
	inline int query(int x)
	{
		return sum[gb(x) - 1] + sum_[x];
	}
}tree,tsum;

inline int solve1(int x)
{
	int Ans = 0;
	int p = tree.query(maxn);
//	cerr<<"*";
	p -= tree.query(x);
//	cerr<<"*";
	Ans += p * x;
	for(int i = 1,r;i <= x;i = r + 1)
	{
		r = x/(x/i);
		int s = tsum.query(r) - tsum.query(i - 1);
		int num = tree.query(r) - tree.query(i - 1);
		Ans += num * x - (x/i) * s;
	}
	return Ans;
}

inline int solve2(int x)
{
	int Ans = tsum.query(x);
	for(int i=x + x;i <=maxn;i += x)
	{
		Ans += tsum.query(i - 1) - tsum.query(i-x);
		int num = tree.query(i - 1) - tree.query(i -x);
		Ans -= num * (i-x);
	}
	return Ans;	
}

signed  main()
{
//	freopen("data.in","r",stdin);
//	freopen("my.out","w",stdout);
//	int d = clock();
//	cerr<<cp;
	int n;
	read(n);
	T = sqrt(3e5);
	tree.Init();
	for(int i=1;i<=n;i++) read(a[i]),maxn = max(maxn,a[i]);
	pk[1] = 0;
//	cerr<<"*";
	maxn = 3e5;
//	bac[a[1]] = 1;
	tree.upd(a[1],1);
	tsum.upd(a[1],a[1]);
	for(int i=2,op;i<=n;i++)
	{
		op = pk[i - 1];
		op += solve1(a[i]);//cerr<<"*";
		op += solve2(a[i]);
		pk[i] = op;
		
		tree.upd(a[i],1);
		tsum.upd(a[i],a[i]);
//		cerr<<"*";
//		cerr<<"*";
	}
	
	for(int i=1;i<=n;i++)
	{
		printf("%lld ",pk[i]);
	}
	
//	cerr<<clock()-d;
 }

//?