这个人站在原地不动,然后不断地用自己的初始吸铁石或者用自己已经吸到的吸铁石来吸;
思路:
先按照质量从小到大排序,然后按照质量分块,块的大小为$sqrt(n)$
对于每一块内,按照距离初始点的距离进行排序,按从小到大排;
然后建立一个队列来BFS,每次对头取出元素,依次扫描每一个块$O(\sqrt{n})$
对于所有块我们分为三种,其中以第k块为分界,k满足:
当$i<k$时,第i块的质量最大值小于等于当前的p,因此每次从头开始找,找到第一个不行的就退出。注意这里需要维护一个头位置,以保证验证过的不会再被循环到,这样子势能均摊复杂度能过够保证每个元素只被考虑一次,因此这一部分的复杂度为o(1)
当$i==k$时,第i块内的质量有大于当前p的,也有小于等于当前p的,这也是我们需要暴力的地方,暴力扫描区间的每一个点,然后更新答案并将被更新的点进行标记。由于每一次都只会暴力长度为sqrt(n)的长度,因此,时间复杂度为O($\sqrt{n}$)
$i\gt k$时,第i块内没有小于等于p的数,因此可以直接不考虑,循环退出。
一共m约等于n次询问,故总的时间复杂度为$O(n\sqrt{n})$
const int N=250010,M=N*2,mod=1e9+7;
int x,y,p,r,n,len,cnt,ans;
int px,py;
struct Seg{
int l,r,mx;
}seg[N];
struct Iron{
int x,y,m,p,r;
}w[N];
queue<Iron> q;
bool st[N]; //存储每一个磁铁的状态
double dist(int a,int b,int xx=x,int yy=y){
double dx=a-xx,dy=b-yy;
return sqrt(1.0*dx*dx+1.0*dy*dy);
}
void solve(){
x=read(),y=read(),p=read(),r=read(),n=read();
px=x,py=y;
rep(i,1,n) {
int x=read(),y=read(),m=read(),p=read(),r=read();
w[i]={x,y,m,p,r};
}
//首先按照质量从大到小排序
sort(w+1,w+1+n,[](Iron &A,Iron &B){
return A.m<B.m;
});
//确定每一块的大小和每一段的信息
len=sqrt(n);
cnt=n/len+(n%len?1:0);
for(int i=1;i<=cnt;++i){
seg[i].l=(i-1)*len+1,seg[i].r=(i!=cnt?i*len:n);
seg[i].mx=w[seg[i].r].m;
sort(w+seg[i].l, w+1+seg[i].r,[](Iron &A,Iron &B){
return dist(A.x,A.y,px,py)<dist(B.x,B.y,px,py);
});
}
q.push({x,y,0,p,r});
while(q.size()){
auto u=q.front(); q.pop();
int x=u.x,y=u.y,p=u.p,rr=u.r;
for(int i=1;i<=cnt;++i){
int &l=seg[i].l, &r=seg[i].r, &mx=seg[i].mx;
if(mx<=p){
for(;l<=r;++l){
if(st[l]) continue;
if(dist(w[l].x,w[l].y)>rr) break;
ans ++; st[l]=true;
q.push({w[l].x,w[l].y,0,w[l].p,w[l].r});
}
}
else if(mx>p){
for(int j=l;j<=r;++j){
if(st[j]) continue;
if(w[j].m<=p&&dist(w[j].x,w[j].y)<=rr){
ans++; st[j]=true;
q.push({w[j].x,w[j].y,0,w[j].p,w[j].r});
}
else if(dist(w[j].x,w[j].y)>rr) break;
}
break;
}
}
}
print(ans);
}