记录编号	121746	评测结果	AAAAAAAAAA
题目名称	[POJ 3145] 永远和谐	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	6.199 s
提交时间	2014-09-21 11:22:21	内存使用	11.14 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int SIZEQ=40010,SIZESQRT=1010,SIZEMX=1000010,INF=0x7fffffff/2;
int Q;
int cmd[SIZEQ]={0},obj[SIZEQ]={0};
int ans[SIZEQ]={0};
int MX,K;
int P[SIZESQRT]={0};
int NX;
int X[SIZEMX]={0};
int ufs[SIZEMX]={0};
int tim[SIZEMX]={0};//插入时间
int grand(int x){
	return !ufs[x]?x:ufs[x]=grand(ufs[x]);
}
int merge(int ga,int gb){
	if(ga>gb) swap(ga,gb);
	ufs[ga]=gb;
}
int getnext(int x){
	return grand(x);
}
int minmod(int y){
	int ansm=INF,ansid=-1;
	for(int k=0;k*y<=MX;k++){
		int now=getnext(k*y);
		if(now==MX+1) continue;
		if(now%y<ansm||(now%y==ansm&&tim[now]>=ansid)){
			ansm=now%y;
			ansid=tim[now];
		}
	}
	return ansid;
}
void calc_2(void){//计算那些>K的询问
	memset(ufs,0,sizeof(ufs));
	X[0]=-1;
	X[NX+1]=MX+1;
	for(int i=1;i<=NX+1;i++)
		for(int j=X[i-1]+1;j<X[i];j++) ufs[j]=X[i];
	for(int i=Q;i>=1;i--){
		if(cmd[i]==2)//添加,这里需要合并区间
			merge(grand(obj[i]),grand(obj[i]+1));
		else if(cmd[i]==1&&obj[i]>K) ans[i]=minmod(obj[i]);
	}
}
int inst[SIZEQ]={0};
void calc_1(void){//计算那些<=K的询问
	for(int i=1;i<=K;i++) P[i]=-1;
	int tot=0;
	for(int i=1;i<=Q;i++){
		if(cmd[i]==2){
			tot++;
			for(int j=1;j<=K;j++){
				if(P[j]==-1||obj[i]%j<=obj[P[j]]%j) P[j]=i;
			}
		}
		else if(cmd[i]==1&&obj[i]<=K){
			if(P[obj[i]]==-1) ans[i]=-1;
			else ans[i]=inst[P[obj[i]]];
		}
	}
}
int kase=0;
void work(void){
	calc_1();
	calc_2();
	if(kase) printf("\n");
	printf("Case %d:\n",++kase);
	for(int i=1;i<=Q;i++)
		if(cmd[i]==1) printf("%d\n",ans[i]);
}
void unique(int s[],int &n){
	int tot=0;
	for(int i=1;i<=n;i++)
		if(i==1||s[i]!=s[i-1]) s[++tot]=s[i];
	n=tot;
}
bool read(void){
	scanf("%d",&Q);
	if(!Q) return false;
	char ch[10];
	MX=0;
	for(int i=1;i<=Q;i++){
		scanf("%s",ch);
		if(ch[0]=='A') cmd[i]=1;
		else if(ch[0]=='B') cmd[i]=2;
		scanf("%d",&obj[i]);
		MX=max(MX,obj[i]);
	}
	K=sqrt(MX+0.5);
	NX=0;
	int tot=0;
	for(int i=1;i<=Q;i++)
		if(cmd[i]==2){
			X[++NX]=obj[i];
			tim[obj[i]]=inst[i]=++tot;
		}
	sort(X+1,X+1+NX);
	tim[MX+1]=-1;
	return true;
}
int main(){
	freopen("harmonyforever.in","r",stdin);
	freopen("harmonyforever.out","w",stdout);
	while(read()) work();
	return 0;
}