用队列实现 “吸取” 这个过程,每次找到能被吸过来的就放到队列最末尾,然后从队头取出当前手上放的
$tips:$ 看到偏序问题,可以往类似
CDQ分治
那种类似的分段排序之类的做法去想吧
需要保证当前手里的吸铁石的磁力和半径分别大于能吸过来的吸铁石的质量和距离
因为变量不对应,我们不好二维偏序之类的套路做法
考虑先按照吸铁石的磁力从小到大排序,这样我们就能找到一个断点 $x$ 满足 $i\le x$ 的质量都小于当前磁力, $i>x$ 的质量都大于磁力
想想距离这一维怎么处理?因为已经找出来了质量小于当前的,只需要考虑距离了,但是如果直接做是 $O(n)$ 的,想办法尽量让每个吸铁石都只被扫过一次,考虑到如果一段距离具有单调性,肯定是选一段前缀而且比较好做,所以我们考虑分块
设将整个序列分为 $\lceil\frac{N}{B}\rceil$ 块,先对于整个序列按照质量为关键字进行排序,再对于每个块,按照距离进行排序
这样我们就一定能找到一个块 $k$ ,满足 $[1,k-1]$ 的块所有石头的质量小于当前磁力, $[k+1,\lceil\frac{N}{B}\rceil]$ 的块中的所有石头大于当前,编号为 $k$ 中的块我们可以单独暴力处理
然后对于 $[1,k-1]$ 的块,每个块我们从块的头开始扫,找到所有距离小于当前半径的,然后把头记到现在为止,下次再扫的时候就不会重复扫描了
$k$ 号块的话暴力处理,然后把没有入队的 按照顺序 记录下来,然后重新覆盖到末尾一段,这样能保证正确性
处理前 $k-1$ 段的复杂度均摊 $O(1)$ 总的为 $O(\sqrt n)$ ,朴素暴力扫描的那一段也是 $O(\sqrt n)$ ,总的就是 $O(n\sqrt n)$
#include<bits/stdc++.h>
#define int long long
using namespace std;
int begintime=clock();
bool __ST__;
int read(){
int res=0;char c=getchar();bool f=0;
while(c<'0' || c>'9') c=='-'?f=1:f=f,c=getchar();
while(c>='0' && c<='9') res=(res<<3)+(res<<1)+c-'0',c=getchar();
return f?-res:res;
}
const int N=25e5+10;
int T=1,n,x0,Y0,P,R,block,t;
int pos[N],st[N],ed[N],now[N],maxnM[N],minnM[N];
struct node{
int m,p,r,dis;
}a[N],PP[N];
queue<node> q;
void solve(){
x0=read(),Y0=read(),P=read(),R=read(),R=R*R,n=read();
block=sqrt(n),t=n/block;
if(n%block) t++;
for(int i=1;i<=t;i++) st[i]=ed[i-1]+1,ed[i]=i*block;
ed[t]=n;
for(int i=1;i<=n;i++){
int x=read(),y=read();
a[i]={read(),read(),read(),0};
a[i].r=a[i].r*a[i].r;
a[i].dis=(x-x0)*(x-x0)+(y-Y0)*(y-Y0);
pos[i]=(i-1)/block+1;
}
sort(a+1,a+n+1,[&](node a,node b){ return a.m==b.m?a.dis<b.dis:a.m<b.m;});
for(int i=1;i<=t;i++){
minnM[i]=a[st[i]].m,maxnM[i]=a[ed[i]].m;
sort(a+st[i],a+ed[i]+1,[&](node a,node b){ return a.dis<b.dis;});
}
q.push({0,P,R,0});
int ans=0;
while(q.size()){
node u=q.front();q.pop();
for(int i=1;i<=t;i++){
if(st[i]>ed[i]) continue ;
if(maxnM[i]<=u.p){
for(;;){
int k=st[i];
if(st[i]>ed[i]){ st[i]=1e9+7;break ;}
if(a[k].dis<=u.r) q.push(a[k]),ans++,st[i]++;
else break ;
}
}else{
int tot=0;
for(int j=st[i];j<=ed[i];j++){
if(a[j].dis<=u.r && a[j].m<=u.p)
ans++,q.push(a[j]);
else PP[++tot]=a[j];
}
st[i]=ed[i]-tot+1;
for(int j=st[i],k=1;j<=ed[i];j++) a[j]=PP[k++];
break ;
}
}
}
printf("%lld",ans);
return ;
}
void clr(){
return ;
}
bool __ED__;
signed main(){
double MEM=((&__ED__)-(&__ST__))/1024.0/1024.0;
fprintf(stderr,"%.2lf MB %.2lf GB\n\n",MEM,MEM/1024.0);
// freopen("in.in","r",stdin);
// freopen("out.out","w",stdout);
// T=read();
while(T--) solve(),clr();
fprintf(stderr,"\n%d ms",clock()-begintime);
return 0;
}