bzoj4320:ShangHai2006 Homework(根号分治+分块)

Author Avatar
Sakits 3月 19, 2018

题解

  第一次真正地写根号分治的题…
  许多这种求倍数的题都是可以用根号分治的,因为设值域为SSx\forall xxSx\geq \sqrt{S}都满足倍数个数S\leq \sqrt{S},而S\leq \sqrt{S}的数又只有S\sqrt{S}个,于是运用这个很好的性质,我们往往可以把复杂度降成根号级别。
  这题对于Y\forall YYSY\leq \sqrt{S},显然可以暴力计算答案,复杂度为O(nS)O(n\sqrt{S}).
  对于Y\forall YY>SY> \sqrt{S}YY的倍数只有S\sqrt{S}个,每次枚举YY的倍数YY',求Y\geq Y'的最小的XX,这个显然可以用分块来维护,做到O(S)O(\sqrt{S})修改,O(1)O(1)查询,总复杂度O(nS)O(n\sqrt{S})

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=500010, maxm=300000, inf=1e9;
int n, blo, x;
int bl[maxn], ans[maxn], mn[maxn], mn2[maxn], v[maxn];
char s[maxn];
inline void read(int &k)
{
	int f=1; k=0; char c=getchar();
	while(c<'0' || c>'9') c=='-' && (f=-1), c=getchar();
	while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
	k*=f;
}
inline int min(int a, int b){return a<b?a:b;}
int main()
{
	read(n); blo=sqrt(maxm);
	for(int i=0;i<=maxm;i++) bl[i]=(i-1)/blo+1, mn2[i]=inf;
	bl[0]=0; mn[0]=inf; for(int i=0;i<=blo;i++) ans[i]=inf;
	for(int i=1;i<=bl[maxm];i++) mn[i]=inf;
	for(int i=1;i<=n;i++)
	{
		scanf("%s", s+1); read(x);
		if(s[1]=='A') 
		{
			for(int j=(bl[x]-1)*blo;j<=x;j++) 
			mn2[j]=min(mn2[j], x);
			for(int j=1;j<=blo;j++)
			ans[j]=min(ans[j], x%j);
			for(int j=0;j<bl[x];j++)
			mn[j]=min(mn[j], x);
		}
		else
		{
			if(x<=blo) printf("%d\n", ans[x]);
			else
			{
				int ans=inf;
				for(int j=0;j<=maxm;j+=x)
				ans=min(ans, min(mn[bl[j]], mn2[j])-j);
				printf("%d\n", ans);
			}
		}
	}
}