codeforces 1207F Remainder Problem

傳送門：http://codeforces.com/problemset/problem/1207/F

5e5也能分塊= =，cf評測姬快如閃電,不過當時也沒時間寫了

又是一道盧總當年講過的big-small思想

len=sqrt(5e5)對于x<len的我們存到數組val[len][len]裡面,O(根号n)修改，O(1)查詢

對于x>len的我們直接在原數組上加，然後O(5e5 / x) 的複雜度，由于x>len,那麼(5e5/len)<=sqrt(5e5)

#include<bits/stdc++.h>
#define maxl 500010

int q,n=maxl-10,len,cnt;
long long ans;
int a[maxl];
long long val[720][720]; 

int main()
{
	len=sqrt(n);
	cnt=cnt/len+1;
	scanf("%d",&q);
	int op,x,y;
	for(int i=1;i<=q;i++)
	{
		scanf("%d%d%d",&op,&x,&y);
		if(op==1)
		{
			a[x]+=y;
			for(int i=1;i<720;i++)
				val[i][x%i]+=y;
		}
		else
		{
			ans=0;
			if(x<720)
				ans=val[x][y];
			else
			{
				for(int i=0;i*x+y<=n;i++)
					ans+=a[i*x+y];
			}
			printf("%lld\n",ans);	
		}
	}
	return 0;	
}