思路： 线段树 （分类讨论）
此题数据很水 数据很水 数据很水
但是卡个暴力还是没问题的……
//By SiriusRen #include <cstdio> #include <cstring> using namespace std; #define maxn 1500000 #define inf 1061109567 int n,tot,jy,xx,yy,tree[maxn*6],vis[maxn],cases,q[maxn]; inline int min(int x,int y){return x<y?x:y;} void insert(int l,int r,int pos){ if(l==r){tree[pos]=l;return;} int mid=(l+r)>>1; if(mid>=jy)insert(l,mid,pos<<1); else insert(mid+1,r,pos<<1|1); tree[pos]=min(tree[pos<<1],tree[pos<<1|1]); } int query(int l,int r,int pos){ if(l>=xx&&r<=yy)return tree[pos]; int mid=(l+r)>>1,lson=pos<<1,rson=pos<<1|1; if(mid<xx)return query(mid+1,r,rson); else if(mid>=yy)return query(l,mid,lson); else return min(query(l,mid,lson),query(mid+1,r,rson)); } int main(){ while(scanf("%d",&n)&&n){ memset(tree,0x3f,sizeof(tree)); memset(vis,0,sizeof(vis)),tot=0; printf("Case %d:\n",++cases); for(int ii=1;ii<=n;ii++){ register char p=getchar(),ch; while(p!='A'&&p!='B')p=getchar(); scanf("%d",&jy); if(p=='B'){ insert(0,maxn,1); vis[jy]=++tot; q[tot]=jy; } else if(p=='A'){ int ans=inf,rec=-1; if(jy<=5000){ for(int i=tot;i;i--){ if(q[i]%jy<ans) ans=q[i]%jy,rec=i; if(!ans)goto end; }goto end; } for(int i=0;i<=1000000;i+=jy){ xx=i,yy=i+jy-1; int temp=query(0,maxn,1); if(temp<inf){ if(ans>temp-i) ans=temp-i,rec=vis[temp]; else if(ans==temp-i&&rec<vis[temp])rec=vis[temp]; } } end:printf("%d\n",rec); } } puts(""); } }
