hdu3303

分析：一个最暴力的想法是把加入到集合S的数据一个个按顺序保存起来，然后每次查询的时候由后向前计算余数，如果遇到余数为0的，就直接把时间输出，否则就一直比较到最后找余数最小时间最晚的，这样查询的时间复杂度是n（当前S的元素个数）。

另一个想法就是利用x、y的数据范围，建线段树表示[1,500000]这个区间，用来更新和查询任意[a,b]区间的最小值。因为[m*y,(m + 1)y - 1]内每个数除y的余数都是唯一的，而且被除数越小余数就越小，所以我们可以查询每个小区间的最小值，再比较应该取哪个时间就可以了。查询的时间复杂度为(maxN/y)*lg(maxN)，可见y越大查询时间越短。但y很小时，就要进行很多次对线段树的查询才能得出结果，所以当y很小时，应该用暴力的方法查询。

  1 #pragma warning(disable:4996)
  2 #include <cstdio>
  3 #include <set>
  4 #include <stack>
  5 #include <vector>
  6 #include <algorithm>
  7 #include <map>
  8 #define maxN 1000001
  9 using namespace std;
 10 int sum[maxN << 1], data[maxN];
 11 int stk[maxN], s;
 12 //向上更新,rt是要更新的节点的下标
 13 void pushUp(int rt){
 14     int m = rt << 1;
 15     if (sum[m] != -1){
 16         sum[rt] = sum[m];
 17     }
 18     else{
 19         sum[rt] = sum[m | 1];
 20     }
 21 }
 22 //初始化线段树
 23 void initTree(int a, int b, int rt){
 24     sum[rt] = -1;
 25     if (a == b){
 26         return;
 27     }
 28     int m = rt << 1;
 29     initTree(a, (a + b) / 2, m);
 30     initTree((a + b) / 2 + 1, b, m | 1);
 31 }
 32 //更新节点
 33 void update(int tgt, int time, int a, int b, int rt){
 34     if (a == b){
 35         sum[rt] = a;
 36         data[a] = time;
 37         return;
 38     }
 39     int m = rt << 1;
 40     if (tgt > (a + b) / 2){//更新右子树
 41         update(tgt, time, (a + b) / 2 + 1, b, m | 1);
 42     }
 43     else{//更新左子树
 44         update(tgt, time, a, (a + b) / 2, m);
 45     }
 46     pushUp(rt);
 47 }
 48 int query(int ta, int tb, int a, int b, int rt){
 49     if (ta <= a && tb >= b || sum[rt] == -1){
 50         return sum[rt];
 51     }
 52     int ret = -1, m = rt << 1;
 53     if (ta <= (a + b) / 2){//查询左子树
 54         ret = query(ta, tb, a, (a + b) / 2, m);
 55     }
 56     if (ret == -1 && tb > (a + b) / 2){//查询右子树
 57         ret = query(ta, tb, (a + b) / 2 + 1, b, m | 1);
 58     }
 59     return ret;
 60 }
 61 int query(int x){
 62     int ret = 0xfffffff, start = 1, end = x - 1,rmdRet = x;
 63     do{
 64         int temp = query(start, end, 1, 1000000, 1);
 65         int rmdTemp = temp % x;
 66         if (temp != -1){
 67             if(rmdRet > rmdTemp){
 68                 rmdRet = rmdTemp;
 69                 ret = temp;
 70             }
 71             else if (rmdRet == rmdTemp && data[ret] < data[temp]){
 72                 ret = temp;
 73             }
 74         }
 75         start = end + 1;
 76         end += x;
 77     }while (end < 1000000);
 78     if (ret == 0xfffffff){
 79         return -1;
 80     }
 81     else{
 82         return data[ret];
 83     }
 84 }
 85 int main(){
 86     int t, x, time;
 87     char op;
 88     int caseNum = 1;
 89     while (scanf("%d", &t), t){
 90         if (caseNum != 1){
 91             printf("
");
 92         }
 93         printf("Case %d:
", caseNum++);
 94         initTree(1, 1000000, 1);
 95         s = 0;
 96         time = 1;
 97         for (int i = 1; i <= t; i++){
 98             scanf("%*c%c%d", &op, &x);
 99             if (op == 'B'){
100                 update(x, time++, 1, 1000000, 1);
101                 stk[s++] = x;
102             }
103             else{
104                 if (x > 2500){
105                     printf("%d
", query(x));
106                 }
107                 else{
108                     int rmd = x,ans = -1;
109                     bool flag = false;
110                     for (int i = s - 1; i >= 0; i--){
111                         if (stk[i] % x == 0){
112                             printf("%d
", i + 1);
113                             flag = true;
114                             break;
115                         }
116                         else if(stk[i] % x < rmd){
117                             rmd = stk[i] % x;
118                             ans = i + 1;
119                         }
120                     }
121                     if (!flag){
122                         printf("%d
", ans);
123                     }
124                 }
125             }
126         }
127     }
128     return 0;
129 }