【CF1553F】Pairwise Modulo

题目描述

You have an array (a) consisting of (n) distinct positive integers, numbered from (1) to (n) . Define (p_k) as

[p_k = sum_{1 le i, j le k} a_i mod a_j, ]

where (x mod y) denotes the remainder when (x) is divided by (y) . You have to find and print (p_1, p_2, ldots, p_n).

思路

首先考虑知道前 (i-1) 个数的 (p_{i-1})，新增一个 (a_i) 会增加 (sum_{j=1}^{i-1}a_j mod a_i+a_i mod a_j)，自然地想到将 (mod) 改为下取整形式，得到

[p_i=p_{i-1}+sum_{j=1}^{i-1}a_j-lfloorfrac{a_j}{a_i} floorcdot a_i+a_i -lfloorfrac{a_i}{a_j} floorcdot a_j ]

记 (s) 为 (a) 的前缀和，即 (s_i=sum_{j=1}^{i}a_j)，则

[p_i=p_{i-1}+s_{i-1}+(i-1)a_i-a_icdotsum_{j=1}^{i-1}lfloorfrac{a_j}{a_i} floor-sum_{j=1}^{i-1}lfloorfrac{a_i}{a_j} floorcdot a_j ]

对于 (a_icdotsum_{j=1}^{i-1}lfloorfrac{a_j}{a_i} floor)，当 (a_jin[dcdot a_i,(d+1)cdot a_i)) 时，(a_j) 对 (a_i) 有 (d) 的贡献，用树状数组维护 (a_j)，枚举 (d) 对区间 ([dcdot a_i,(d+1)cdot a_i)) 求和，然后单点修改插入 (a_i).

对于 (sum_{j=1}^{i-1}lfloorfrac{a_i}{a_j} floorcdot a_j)，当 (a_iin[dcdot a_j,(d+1)cdot a_j)) 时，(a_j) 对 (a_i) 有 (a_jcdot d) 的贡献，用树状数组维护每个 (a_j) 对其他位置贡献，单点查询 (a_i)，然后枚举 (d) 区间修改，将区间 ([dcdot a_i,(d+1)cdot a_i)) 加上 (a_icdot d).

刚做这题时一直在想除法分块，除法分块是考虑 (lfloorfrac{n}{i} floor) 中，(n) 一定时 (i) 在某些范围内会使下取整的值相同，这样做的话只能处理 (sum_{j=1}^{i-1}lfloorfrac{a_i}{a_j} floorcdot a_j) 这个式子，因为另一个式子的分子是 (a_j) 是不定的. 而本题则换了个思路，考虑分子是什么范围内时有相同的贡献.

枚举 (d) 看上去很暴力，对于一个 (a_i) 会枚举 (lfloorfrac{3cdot 10^5}{a_i} floor) 次，但是由于 (a_i) 互不相同，所以复杂度是调和级数级别的.

#include <algorithm>
#include <cstdio>
#define int long long
using namespace std;
const int maxn = 3e5 + 10;
int n,pre,ans;
struct fenwick {
	int c[maxn];
	inline void add(int x,int v) {
		for (;x <= maxn;x += x&(-x)) c[x] += v;
	}
	inline int sum(int x) {
		int res = 0;
		for (;x;x -= x&(-x)) res += c[x];
		return res;
	}
} q,p;
signed main() {
	scanf("%lld",&n);
	for (int i = 1,x;i <= n;i++) {
		scanf("%lld",&x);
		ans += pre+(i-1)*x-p.sum(x);
		pre += x;
		for (int d = 1;d*x <= maxn;d++)
			ans -= x*d*(q.sum(min((d+1)*x,maxn)-1)-q.sum(d*x-1));
		printf("%lld%c",ans,i ^ n ? ' ' : '
');
		q.add(x,1);
		for (int d = 1;d*x <= maxn;d++) {
			p.add(d*x,d*x);
			p.add(min((d+1)*x,maxn),-d*x);
		}
	}
	return 0;
}