悬关,stl入门语法问题(?
查看原帖
悬关,stl入门语法问题(?
756805
xuweiyi楼主2024/8/9 22:31

二分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常数)
2024/8/9 22:31
加载中...