【BZOJ4320】ShangHai2006 Homework

Description

1：在人物集合 S 中加入一个新的程序员，其代号为 X,保证 X 在当前集合中不存在。

2：在当前的人物集合中询问程序员的mod Y 最小的值。（为什么统计这个？因为拯救过世界的人太多了，只能取模）

Input

第一行为用空格隔开的一个个正整数 N。

接下来有 N 行，若该行第一个字符为“A” ，则表示操作 1；若为“B”，表示操作 2；

其中对于 100%的数据：N≤100000， 1≤X,Y≤300000，保证第二行为操作 1。

Output

对于操作 2，每行输出一个合法答案。

Sample Input

5
A 3
A 5
B 6
A 9
B 4

Sample Output

3
1

HINT

【样例说明】

在第三行的操作前，集合里有 3、5 两个代号，此时 mod 6 最小的值是 3 mod 6 = 3；

在第五行的操作前，集合里有 3、5、9，此时 mod 4 最小的值是 5 mod 4 = 1；

题解：第一眼看题就想到分段，看题解要用并查集一下子就怂了，不过点进去之后发现还是分段。。。

设m表示x的最大值，对于y<=sqrt(m)的询问，我们可以开个桶，每次暴力维护，对于y>sqrt(m)的询问，我们可以枚举(x/y)*y的位置，然后找到比它大的，最近的x，这就要用到并查集。考虑离线处理，将加点变成删点，每删除一个点就相当于把两个小区间合并。我们查找的时候找的就是区间的右端点。

#include <cstdio>

#include <cstring>

#include <iostream>

using namespace std;

int n,m,siz;

int f[300010],ans[100010],q[100010],vis[300010],st[410];

char str[10];

int find(int x)

{

	return (f[x]==x)?x:(f[x]=find(f[x]));

}

int main()

{

	scanf("%d",&n);

	siz=400;

	int i,j;

	memset(st,0x3f,sizeof(st));

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

	{

		scanf("%s%d",str,&q[i]);

		if(str[0]=='A')

		{

			for(j=1;j<=siz;j++)	st[j]=min(st[j],q[i]%j);

			m=max(m,q[i]),vis[q[i]]=1,q[i]=-q[i];

		}

		else	if(q[i]<=siz)	ans[i]=st[q[i]];

	}

	for(i=0;i<=m+1;i++)	f[i]=(vis[i])?i:i+1;

	for(i=n;i>=1;i--)

	{

		if(q[i]<0)	f[-q[i]]=find(-q[i]+1);

		else

		{

			if(q[i]>siz)

			{

				ans[i]=1<<30;

				for(j=0;j<=m;j+=q[i])	ans[i]=min(ans[i],find(j)%q[i]);

			}

		}

	}

	for(i=1;i<=n;i++)	if(q[i]>0)	printf("%d\n",ans[i]);

	return 0;

}

巴特西

【BZOJ4320】ShangHai2006 Homework 分段+并查集