題目鏈接：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;
}