首页 > 代码库 > 【BZOJ4320】ShangHai2006 Homework 分段+并查集

【BZOJ4320】ShangHai2006 Homework 分段+并查集

2024-10-13 02:39:39   214人阅读

【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 分段+并查集


联系
我们