poj3145

  1 /*
  2 这一题有点坑，刚开始的时候就想着对于每一个y分成n/y段来统计，
  3 但是发现y很小的时候效率很糟糕，然后就想不出了，以为会有什么超绝的想法
  4 或者结合数论来搞，然后就是糟糕的百度题解！！
  5 发现y很小的时候直接暴力，这效率能行么，对于算时间复杂度我是完全不会的，
  6 暴力时间O(n)，用线段树时间 O(N/Y*log(N));只能说y取10^3的时候两者时间差不多，
  7 最后感觉是卡过的，但又因为有插入操作，如果都是询问的或者都是插入的话时间大概为10^8
  8 然后如果有一半插入的话，时间就更短，所以应该可以吧； 
  9 
 10 */
 11 
 12 
 13 #include<cstdio>
 14 #include<cstring>
 15 #include<cstdlib>
 16 #include<iostream>
 17 #include<algorithm>
 18 #include<cmath>
 19 #define lson l,m,rt<<1
 20 #define rson m+1,r,rt<<1|1
 21 using namespace std;
 22 const int N=500000+10;
 23 //const int Maxn=40000+10;
 24 const int limt=1000;
 25 int minv[N<<2],n;
 26 int ti[N],vi[N],sz;
 27 void pushup(int rt){
 28     minv[rt]=min(minv[rt<<1],minv[rt<<1|1]);
 29 }
 30 void update(int L,int R,int v,int l,int r,int rt){
 31     if (L<=l && r<=R){
 32         minv[rt]=v;
 33         return;
 34     }
 35     int m=(l+r)>>1;
 36     if (L<=m) update(L,R,v,lson);
 37     if (m< R) update(L,R,v,rson);
 38     pushup(rt);
 39 }
 40 void query1(int y){
 41     int ret=-1,tmp=-1; 
 42     for (int i=sz-1;i>=0;i--){
 43         if (vi[i]%y==0) {
 44             ret=i;break;
 45         }
 46         if (tmp==-1 || (vi[i]%y)<tmp) {
 47             tmp=vi[i]%y;ret=i;
 48         }
 49     }
 50     printf("%d\n",ret+(ret==-1?0:1));
 51 }
 52 int query3(int L,int R,int l,int r,int rt){
 53     if(L<=l && r<=R){
 54         return minv[rt];
 55     }
 56     int m=(l+r)>>1;
 57     int t1,t2;
 58     t1=t2=N;
 59     if (L<=m) t1=query3(L,R,lson);
 60     if (m< R) t2=query3(L,R,rson);
 61      return min(t1,t2);   
 62 }
 63 void query2(int y){
 64     int t,ret=-1;
 65     for (int i=0;i<N;i+=y){
 66     //    cout<<i<<" "<<i+y-1<<endl;
 67         if (i+y-1>N) t=query3(i,N-1,0,N-1,1);
 68         else t=query3(i,i+y-1,0,N-1,1);
 69         if (t==N) continue;
 70     //    cout<<"** "<<t<<endl;
 71         if (t%y<ret%y || ret==-1) ret=t;
 72         else if (t%y==ret%y && ti[t]>ti[ret]) ret=t;
 73     }
 74 //    cout<<ret<<endl;
 75     if (ret==-1) printf("-1\n");
 76     else printf("%d\n",ti[ret]);
 77 }
 78 int main(){
 79     
 80     int T,cas=0;
 81     while (~scanf("%d",&n),n){
 82         if (cas!=0 && n!=0) printf("\n");
 83         sz=0;
 84         for (int i=0;i<(N<<2);i++) minv[i]=N;
 85         printf("Case %d:\n",++cas);
 86         for (int i=0;i<n;i++){
 87             char s[10];int x;
 88             scanf("%s%d",s,&x);
 89             if (s[0]=='A'){
 90                 if (x<limt) query1(x);
 91                 else query2(x);
 92             }else if (s[0]=='B'){
 93                 vi[sz]=x;
 94                 ti[x]=sz+1;    
 95                 update(x,x,x,0,N-1,1);
 96                 sz++;
 97             }
 98         }
 99     }
100     return 0;
101 }