【分块】洛古 P3396 哈希冲突

题链

$p[i][j]$ 表示 $mod$ 为 $i$,池子为 $j$ 的总和，可以预处理 $mod$ 在 $[1,1000]$ 范围内的答案，$O(1)$回答每个询问；

如果询问的范围超过了 $1000$，则暴力跑一边即可；

复杂度顶得住…

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define ll long long
#define ULL unsigned long long
#define Pair pair<LL,LL>
#define ls rt<<1
#define rs rt<<1|1
#define Pi acos(-1.0)
#define eps 1e-6
#define DBINF 1e100
#define mod 998244353
#define MAXN 1e18
#define MS 150009

int n,m;
int a[MS];
int p[1009][1009]; 

void init(){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=1001;j++){
			p[j][i%j] += a[i];
		}
	}
}

void update(int pos,int val){
	for(int i=1;i<=1001;i++){
		p[i][pos%i] -= a[pos];
		p[i][pos%i] += val;
	}
	a[pos] = val;
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for(int i=1;i<=n;i++){
		cin >> a[i];
	}
	init();
	while(m--){
		char op;
		int x,tar;
		cin >> op >> x >> tar;
		if(op == 'A'){
			if(x >= 1001){
				int ans = 0;
				for(int i=tar;i<=n;i+=x){
					ans += a[i];
				}
				cout << ans << "\n";
			} 
			else cout << p[x][tar] << "\n";
		}
		else{
			update(x,tar);
		}
	}
	
	return 0;
}