题目链接：http://poj.org/problem?id=3145
/**//*
题意：
对于一个集合S，一共两种操作：
1. B X: 添加一个数X到S. 第K个B操作发生在第K个时间点，并且每个之前S集合中没有X。
2. A Y: 在S集合中所有数中, 被Y除后余数最小的，如果有相同的，选择最近插入的那个
数，如果没有则输出-1
题解：
树状数组 或者 线段树
思路：
这题主要看怎么去平衡了。如果数据量很小，可以直接开一个一维数组，下标表示除
数Y，每次B操作的时候遍历一遍该数组，将答案存下来。但是当插入操作很多的时候这个
复杂度就比较大了，因为数字的范围是(1 <= X, Y <= 500000)，每次都执行插入操作，并
且遍历整个数组进行更新的话总的执行次数就是500000^2，于是可以换个角度，想想其他
办法，用每个数的值作为树状数组的下标，每次B操作就将该数插入到树状数组中，等到A
操作进行询问时，利用树状数组的成段求和，统计[0, Y-1]、[Y, 2*Y-1] 
这些区间段
中最小的sum不为0的数，然后取一个最小值。这样的方法当Y很大的时候复杂度是很小的，
但是如果Y是1的话就退化成O(n)了。于是我们可以将以上两种方法结合一下，Y的值比较小
的时候存在数组中，即使读取，大的时候利用树状数组+二分进行统计找出最小值。
这个平衡的系数可以取sqrt(50000)，但是关键还是要看题目的数据，所以如果超时就
左右稍作调整即可。
*/
#include <iostream>
using namespace std;
#define mod_split 6208
#define maxn 500010
int n;
int ans[mod_split + 1], tim[ mod_split + 1 ];
int c[maxn];
int nt[maxn];
inline int lowbit(int x) {
return x & (-x);
}
void add(int pos) {
while(pos < maxn) {
++c[pos];
pos += lowbit(pos);
}
return ;
}
int sum(int pos) {
int s = 0;
while(pos > 0) {
s += c[pos];
pos -= lowbit(pos);
}
return s;
}
int Bin(int l, int r) {
if(!l) l++;
if(l >= maxn) l = maxn - 1;
if(r >= maxn) r = maxn - 1;
int ans = -1;
int pre = sum(l - 1);
while(l <= r) {
int m = (l + r) >> 1;
if(sum(m) - pre > 0) {
r = m - 1;
ans = m;
}else
l = m + 1;
}
return ans;
}
int main() {
int i, j;
int Case = 1;
while(scanf("%d", &n) != EOF && n) {
if(Case != 1)
puts("");
for(j = 0; j <= mod_split; j++) {
ans[j] = mod_split + 1;
tim[j] = -1;
}
memset(c, 0, sizeof(c));
printf("Case %d:\n", Case ++ );
int Time = 0;
for(i = 1; i <= n; i++) {
char str[10];
int x;
scanf("%s %d", str, &x);
if(str[0] == 'B') {
Time ++;
for(j = 1; j <= mod_split; j++) {
int p = x % j;
if(p <= ans[j]) {
ans[j] = p;
tim[j] = Time;
}
}
add(x);
nt[x] = Time;
}else {
if(x <= mod_split) {
printf("%d\n", tim[x]);
}else {
int l = 0, r = x - 1;
int MinVal = -1;
int MinTime;
while(1) {
int v = Bin(l, r);
if(v != -1) {
int Mod = v % x;
if(Mod < MinVal || MinVal == -1) {
MinVal = Mod;
MinTime = nt[v];
}else if(Mod == MinVal) {
if(MinTime < nt[v])
MinTime = nt[v];
}
}
if(l >= maxn || r >= maxn)
break;
l += x;
r += x;
}
if(MinVal != -1)
printf("%d\n", MinTime);
else
printf("-1\n");
}
}
}
}
return 0;
}