BZOJ 4320 ShangHai2006 Homework

题目大意

请你维护一个集合，支持以下操作：

1. 加入一个元素$x$
2. 求$\mod x$最小的元素

这题首先因为求的是模意义下的最小值，每次的模数都不一样，所以自然不能用基础的数据结构或者类似的东西进行维护。又因为数据范围极大，不好用一些奇奇怪怪的方法维护，所以考虑分治的方法。

对于小于$\sqrt{n}$的询问，使用数组记录一下就OK了，时间复杂度$O(\sqrt{n})$

对于大于$\sqrt{n}$的询问，考虑枚举$ax$，求出距离其最近的一个数就OK了。使用并查集维护，时间复杂度是$O(\sqrt{n}\log n)$的。

总时间复杂度$O(n\sqrt{n}\log n)$.

#include <cmath>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using namespace std;
inline char nc()
{
	static char buf[100000],*p1,*p2;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,10000,stdin),p1==p2)?EOF:*p1++;
}
inline int ri()
{
	int ret=0;char tmp=nc();
	while(!isdigit(tmp)) tmp=nc();
	while(isdigit(tmp)) ret=ret*10+(tmp-'0'),tmp=nc();
	return ret;
}
inline char ric()
{
	char ret=nc();
	while(!isalpha(ret)) ret=nc();
	return ret;
}
int n,lim,buc[300010],res[100010],fa[300010],minn=0x3f3f3f3f;
char opt[100010];int x[100010];
int unifind(int x){return fa[x]==x?x:fa[x]=unifind(fa[x]);}
int main()
{
	memset(buc,0x3f,sizeof buc);
	memset(res,0x3f,sizeof res);
	int i,j;
	n=ri(),lim=400;
	for(i=1;i<=n;++i) opt[i]=ric(),x[i]=ri();
	for(i=1;i<=n;++i)
	{
		if(opt[i]=='A')
		{
			minn=min(minn,x[i]);
			for(j=1;j<=lim;++j)
				buc[j]=min(buc[j],x[i]%j);
		}
		else
		{
			res[i]=min(res[i],minn);
			if(x[i]<=lim)
				res[i]=min(res[i],buc[x[i]]);
		}
	}
	for(i=1;i<=n;++i) if(opt[i]=='A') fa[x[i]]=x[i];
	for(i=j=300000;i;--i)
	{
		if(fa[i]==i) j=i;
		else fa[i]=j;
	}
	for(i=n;i>=1;--i)
	{
		if(opt[i]=='A')
			j=unifind(x[i]),fa[j]=unifind(j+1);
		else
		{
			if(x[i]>lim)
				for(j=x[i];j<=300000;j+=x[i])
					if(unifind(j)!=300000)
						res[i]=min(res[i],unifind(j)%x[i]);
		}
	}
	for(i=1;i<=n;++i)
		if(opt[i]=='B')
			printf("%d\n",res[i]);
	return 0;
}