【题解】哈希冲突

题目戳我

( ext{Solution:})

题目大意是求，单点修改，(sum_{i=1}^n a[i][imod x=y])

考虑根号分治：对(x)分类讨论。

当(xleq sqrt{n})时，设(sum[i][j])表示模(i)为(j)的所有数之和。这一部分可以(O(nsqrt n))预处理，(O(sqrt n))修改。

当(x>sqrt{n})时，考虑暴力的复杂度：有效的(pos)只有(frac{n}{x})个，这一部分一定小于等于(sqrt{n}.)

所以，总复杂度应为(O((n+m)sqrt n).)

#include<bits/stdc++.h>
using namespace std;
int n,m;
int sum[500][500],a[150001];
void solve(int x,int y){
	int Ans=0;
	for(int i=y;i<=n;i+=x)Ans+=a[i];
	printf("%d
",Ans);
}
int main(){
	scanf("%d%d",&n,&m);
	int N=sqrt(n)+1;
	for(int i=1;i<=n;++i)scanf("%d",&a[i]);
	for(int i=1;i<=N;++i){
		for(int j=1;j<=n;++j){
			sum[i][j%i]+=a[j];
		}
	}
	while(m--){
		int x,y;
		char c;
		cin>>c;
		scanf("%d%d",&x,&y);
		if(c=='A'){
			if(x<=N)printf("%d
",sum[x][y]);
			else solve(x,y);
		}
		else{
			for(int i=1;i<=N;++i)sum[i][x%i]+=(y-a[x]);
			a[x]=y;
		}
	}
	return 0;
}