磁力块[分块]

本文主要是介绍磁力块[分块]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门

---

题解原网 

 遵从大段一起跳,小段暴力跳

---

#include<bits/stdc++.h>
#define N 250050
#define LL long long
using namespace std;
LL X0,Y0,pl,rl,n,len,vis[N];
LL L[N],R[N],D[N],tot,q[N];
struct Node{LL d,r,m,p;}x[N]; 
LL read(){ LL cnt=0,f=1;char ch=0;while(!isdigit(ch)){ch=getchar();if(ch=='-') f=-1;}while(isdigit(ch))cnt=cnt*10+(ch-'0'),ch=getchar();return cnt*f;
}
LL calc(LL x,LL y){return (x-X0)*(x-X0)+(y-Y0)*(y-Y0);}
bool cmp1(Node x,Node y){return x.d<y.d;}
bool cmp2(Node x,Node y){return x.m<y.m;}
int main(){X0=read(),Y0=read(),x[0].p=read(),x[0].r=read(),n=read(); x[0].r *= x[0].r;for(int i=1;i<=n;i++){LL a=read(),b=read();x[i].d=calc(a,b),x[i].m=read(),x[i].p=read(),x[i].r=read();x[i].r *= x[i].r;}sort(x+1,x+n+1,cmp1); len=int(sqrt(n));for(int i=1;i<=n;i+=len){L[++tot]=i,R[tot]=min(i+len-1,n),D[tot]=x[R[tot]].d;sort(x+L[tot],x+R[tot]+1,cmp2);}int l=1,r=1; q[1]=0;while(l<=r){LL u=q[l] , limit=x[u].r , p=x[u].p; l++;for(int i=1;i<=tot;i++){if(D[i]>limit){for(LL j=L[i];j<=R[i];j++)if(!vis[j] && x[j].m<=p && x[j].d<=limit) q[++r]=j,vis[j]=1;	break;}while(L[i]<=R[i] && x[L[i]].m<=p){if(!vis[L[i]]) vis[L[i]]=1,q[++r]=L[i];L[i]++;}}}printf("%d",r-1); return 0;
}

 

这篇关于磁力块[分块]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---