二分set出现死循环
萌新不太会stl,网上没查到。(如不是stl问题,勿喷)
具体问题在代码中有写,十分感谢
#start
#include<bits/stdc++.h>
using namespace std;
#define fr(fgh,asd,i) for(int i=fgh,i##end=asd;i<=i##end;++i)
typedef long long ll;
int q;set<int>st;
const int B=2500;
int a[B+5];
inline int mi(int x,int y) {return x>y?y:x;}
int main(){
ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
cin>>q;char op;int x;
fr(1,B,i) a[i]=i;
while(q--){
cin>>op>>x;
if(op=='A'){
st.insert(x);
fr(1,B,i){
a[i]=mi(a[i],x%i);
}
}else{
if(x<=B) printf("%d\n",a[x]);
else{int ans=x;
for(ll i=0;;i+=x){
auto p=st.lower_bound(i);
auto p1=lower_bound(st.begin(),st.end(),i);
if(p==st.end()) break;//此为通过代码,改成p1 tle/pts:10
ans=mi(ans,*p-i);
}printf("%d\n",ans);
}
}
}
return 0;
}//qy(y=3e5) qS(S=3e5)
//令 y<=500,暴力,即预处理输出
//y>=500,对于每个500,查询最小模数
//具体而言,对于每个块内,二分查找第一个满足要求的数
//这里是q*B修改,q*n/B*logq或q查询,考虑让B偏大,系数差距为18,故令B=2500(考虑set常数)