原题连接
更好的阅读体验

题目描述

在一片广袤无垠的原野上，散落着N块磁石。

每个磁石的性质可以用一个五元组(x,y,m,p,r)描述，其中x,y表示其坐标，m是磁石的质量，p是磁力，r是吸引半径。

若磁石A与磁石B的距离不大于磁石A的吸引半径，并且磁石B的质量不大于磁石A的磁力，那么A可以吸引B。

小取酒带着一块自己的磁石L来到了这片原野的$(x0,y0)$处，我们可以视磁石L的坐标为$(x0,y0)$。

小取酒手持磁石L并保持原地不动，所有可以被L吸引的磁石将会被吸引过来。

在每个时刻，他可以选择更换任意一块自己已经获得的磁石（当然也可以是自己最初携带的L磁石）在$(x0,y0)$处吸引更多的磁石。

小取酒想知道，他最多能获得多少块磁石呢？

输入格式
第一行五个整数$x0$,$y0$,$pL$,$rL$,$N$，表示小取酒所在的位置，磁石L磁力、吸引半径和原野上散落磁石的个数。

接下来$N$行每行五个整数$x$,$y$,$m$,$p$,$r$，描述一块磁石的性质。

输出格式
输出一个整数，表示最多可以获得的散落磁石个数（不包含最初携带的磁石L）。

数据范围
$1≤N≤250000$
$−10^9≤x,y≤10^9$
$1≤m,p,r≤10^9$

样例

输入样例：
0 0 5 10 5
5 4 7 11 5
-7 1 4 7 8
0 2 13 5 6
2 -3 9 3 4
13 5 1 9 9
输出样例：
3

分块+广度优先搜索 $O(N\sqrt{n})$

这道题目的数据范围又大,区间操作很明显,而且似乎线段树和树状数组又不好处理这道题目,所以我们只好运用,大块维护,小块枚举的分块思想了.

首先我们看得到的条件是.$质量 \le 磁力,距离 \le 吸引半径$

既然如此的话,我们不妨先把这N块磁铁石按照质量排序,分成$\sqrt{n}$段,然后在每一段的内部,再按照距离排序.

我们可以开一个队列,这个队列刚开始只有赠送磁石,那么每次我们就可以取出队头,然后将队头可以吸引的磁石统统存储入队列之中即可.然后因为每一段内部已经按照距离排好序了.

设队头磁铁石为H,那么必然存在一个K,满足一下这些性质

1. 第1~K-1段中所有的磁石质量都不大与H的磁力
2. 第K+1段之后的磁铁石质量都大于H的磁力

所以来说第1~K-1段中与$(x_0,y_0)$距离小于H的必定是处于每段的开头

那么我们从左往右数,发现如果无法吸引过来了,那么下一次我们直接把这段的开头位置移到这个无法吸引的位置.

C++ 代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=2e6;
const int w=500;
struct node
{
    ll d,r;
    ll m,p;
} a[N];
ll D[N],x0,y_0,now,L[N],R[N],v[N],n,tot,l,r,p,x,y;
queue<ll> q;
bool cmp_d(node a,node b)
{
    return a.d<b.d;
}
bool cmp_m(node a,node b)
{
    return a.m<b.m;
}
int main()
{
    cin>>x0>>y_0>>a[0].p>>a[0].r>>n;
    a[0].r*=a[0].r;//第一块磁铁
    for(int i=1;i<=n;i++)
    {
        cin>>x>>y>>a[i].m>>a[i].p>>a[i].r;
        a[i].r*=a[i].r;
        a[i].d=(x0-x)*(x0-x)+(y_0-y)*(y_0-y);//计算距离
    }
    sort(a+1,a+1+n,cmp_d);
    for(ll i=1;i<=n;i+=w)
    {
        L[++tot]=i;
        R[tot]=min(n,i+w-1);//计算L和R的范围,也就是第i大块的范围
        D[tot]=a[R[tot]].d;
        sort(a+L[tot],a+R[tot]+1,cmp_m);//大块内则排序
    }
    q.push(0);
    ll ans=1;
    while(q.size())
    {
        ll l=q.front();
        now=a[l].r;
        p=a[l].p;
        q.pop();
        for(ll i=1;i<=tot;i++)
        {
            if (D[i]>now)
            {
                for(ll j=L[i];j<=R[i];j++)
                    if (!v[j] && a[j].d<=now && a[j].m<=p)//没有吸过来,而且在范围内
                    {
                        q.push(j);
                        ans++;
                        v[j]=1;
                    }
                break;
            }
            while(L[i]<=R[i] && a[L[i]].m<=p)//加入一块磁铁石,然后把则块磁铁石可以吸收的磁铁石放进去
            {
                if (!v[L[i]])//没有被访问
                {
                    q.push(L[i]);
                    ans++;
                }
                ++L[i];
            }
        }
    }
    cout<<ans-1;//不算刚开始的赠送磁石
}