题目描述
blablabla
样例
blablabla
算法 分块
$O(nsqrt(n))$
blablabla
时间复杂度
参考文献:算法竞赛进阶指南
C++ 代码
#include<bits/stdc++.h>
using namespace std;
#define go(i,a,b) for(int i=a;i<=b;++i)
#define com(i,a,b) for(int i=a;i>=b;--i)
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;
const int N=250000+10;
int n,ans=0;
bool vis[N];
int L[N],R[N],M[N];
struct node{
int x,y,m,p,r;
#define x(i) p[i].x
#define y(i) p[i].y
#define m(i) p[i].m
#define p(i) p[i].p
#define r(i) p[i].r
}p[N];
queue<int>q;
template<typename T> inline void read(T &x){
x=0;char f=1,c=getchar();
while(!isdigit(c)){ if(c=='-') f=-1; c=getchar(); }
while(isdigit(c)){ x=x*10+c-'0'; c=getchar(); }
x*=f;
}
ll d(const node &a){
return (ll)(a.x-x(0))*(a.x-x(0))+(ll)(a.y-y(0))*(a.y-y(0));
}
bool cmp(const node &a,const node &b){ return a.m<b.m; }
bool cmp2(const node &a,const node &b){ return d(a)<d(b); }
signed main(){
//freopen("input.txt","r",stdin);
cin>>p[0].x>>p[0].y>>p[0].p>>p[0].r>>n;
go(i,1,n)
read(x(i)),read(y(i)),read(m(i)),read(p(i)),read(r(i));
int t=sqrt(n*1.0);
sort(p+1,p+n+1,cmp);
go(i,1,t)
L[i]=R[i-1]+1,R[i]=i*t,M[i]=m(R[i]),sort(p+L[i],p+R[i]+1,cmp2);
if(R[t]<n){
L[++t]=R[t-1]+1;
R[t]=n;
M[t]=m(R[t]);
sort(p+L[t],p+R[t]+1,cmp2);
}
vis[0]=1;q.push(0);
while(!q.empty()){
int now=q.front();
q.pop();
int k=0;
for (int i = 1; i <= t; i++)//k一定要<=t
if (M[i] <= p(now)) k = i;
else break;
go(i,1,k){
while(L[i]<=R[i]&&d(p[L[i]])<=(ll)r(now)*r(now)){
if(!vis[L[i]]) vis[L[i]]=1,q.push(L[i]),++ans;
++L[i];
}
}
if(t!=k++){
go(i,L[k],R[k]){
if(!vis[i]&&d(p[i])<=(ll)r(now)*r(now)&&m(i)<=p(now)) vis[i]=1,q.push(i),++ans;
}
}
}
cout<<ans;
return 0;
}