P 3396 哈希冲突 根号分治

Link

据说这是一道论文题？？？？。具体论文好像是 集训队论文《根号算法——不只是分块》

根号分治的裸题。

首先我们考虑暴力怎么打。

• 先预处理出每个模数的答案，之后再 O（1） 的回答，修改预处理O(\(n^2\))
• 每次询问直接暴力统计，修改是 O (1) 的，但回答是O(\(n^2\)) 的。

这两种写法都不能通过此题。

那我们想办法把询问和修改的复杂度均摊一下。

对于模数比较少的数，我们直接暴力统计的话，会涉及到的数比较多，这样时间复杂度就上去了，所以我们采用方法一，来减少询问的复杂度。

对于模数比较大·的数，我们就可以直接暴力回答，因为涉及到的数不会太多，这样我们的复杂度是完全可以接受的。

我们一般把这个阈值设为 \(\sqrt{n}\) ，比这个数大的，我们认为他是比较大的模数，直接暴力统计答案的询问最多涉及到 \({n \over {\sqrt n}} = \sqrt n\) 个数。

总的复杂度为 \(O((n+m)\sqrt n)\)

Code

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

using namespace std;

#define LL long long

int n,m,x,y,maxn,T,a[150010],f[400][400], ans;

inline int read()

{

	int s =  0,w = 1; char ch = getchar();

	while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}

	while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0'; ch = getchar();}

	return s * w;

}

int main(){

	n = read(); m = read(); T = sqrt(n);

	for(int i = 1; i <= n; i++)

	{

		a[i] = read();

		for(int p = 1; p <= T; p++)//模数比较小的数，先预处理出答案来

		{

			f[p][i % p] += a[i];

		}

	}

	for(int i = 1; i <= m; i++)

	{

		char opt; cin>>opt;

		x = read(); y = read();

		if(opt == 'A')

		{

			if(x <= T) printf("%d\n",f[x][y]);//模数小的数可以直接回答

			else

			{

				ans = 0;

				for(int j = y; j <= n; j += x)//模数比较大的数暴力统计

				{

					ans += a[j];

				}

				printf("%d\n",ans);

			}

		}

		else if(opt == 'C')

		{

			for(int p = 1; p <= T; p++)

			{

				f[p][x % p] += y - a[x];//增量法对预处理的值修改

			}

			a[x] = y;

		}

	}

	return 0;

}