磁力块

重点是bfs,分块只是优化bfs.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=2e5+6e4;
const ll M=500;//块的大小
struct vv{
    ll d,p,r,m;//距离 磁力 半径 质量
}a[N];

ll L[M],R[M],D[M];//每个块的左边和右边.每个块最右边的质量
bool vis[N];
queue<ll>q;//队列

bool cnp(vv x,vv y)
{
    return x.d<y.d;//距离排序
}

bool cmp(vv x,vv y)
{
    return x.m<y.m;//质量排序
}

int main()
{
    ll x0,y0,pl,rl,n,tot=0;
    scanf("%lld%lld%lld%lld%lld",&x0,&y0,&pl,&rl,&n);//(x0,y0)是这个点 pl是你现在的磁力,rl是你的半径,
    a[0].p=pl;a[0].r=rl*rl;
    q.push(0);
    for(ll i=1;i<=n;i++)
    {
        ll x1,x2,x3,x4,x5;
        scanf("%lld%lld%lld%lld%lld",&x1,&x2,&x3,&x4,&x5);
        a[i].d=(x1-x0)*(x1-x0)+(x2-y0)*(x2-y0);//距离
        a[i].m=x3;a[i].p=x4;a[i].r=x5*x5;
    }
    sort(a+1,a+1+n,cnp);//按距离排序.
    for(ll i=1;i<=n;i+=M)
    {
        L[++tot]=i;
        R[tot]=min(n,i+M-1);
        D[tot]=a[R[tot]].d;
        sort(a+L[tot],a+R[tot]+1,cmp);//把每块的质量进行排序.
    }//tot块.
    ll ans=0;
    while(q.size())//bfs
    {
        ll temp=q.front();
        ll pos=a[temp].r;
        ll mat=a[temp].p;
        q.pop();
        for(ll i=1;i<=tot;i++)
        {
            if(D[i]>pos)//假如说我的最右边的距离已经＞我能所控制的距离,那么直接统计下这段符合
            {
                for(ll j=L[i];j<=R[i];j++)
                {
                    if(!vis[j]&&mat>=a[j].m&&a[j].d<=pos)
                    {
                        q.push(j);
                        ans++;
                        vis[j]=1;
                    }
                }
                break;
            }
            while(mat>=a[L[i]].m&&L[i]<=R[i])
            {
                if(!vis[L[i]])
                {
                    q.push(L[i]);
                    ans++;
                }
                L[i]++;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}