题目链接

输入格式

第一行五个整数 $x_0,y_0,p_L,r_L,N$，表示小取酒所在的位置，磁石 $L$ 磁力、吸引半径和原野上散落磁石的个数。

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

输出格式

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

数据范围

$1\le N\le 250000,$
$-10^9\le x,y\le 10^9,$
$1\le m,p,r\le 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

思路

如果磁石的属性只有重量 $m$ 这一维，那么根据 $m$ 从小到大排序，将已有的磁石加入队列，从小到大扫描排序后的磁石，若能吸引第 $i$ 个磁石，则将其加入队列，并且记录前 $i$ 个磁石都已被吸引。不断用队首的磁石进行这一操作，就可以计算出最终能吸引的磁石的数量。

但是，这题多了距离 $r$ 这个因素，如果依旧按照上面的方法，无法保证吸引第 $i$ 块磁石后，前 $i$ 块磁石都可以被吸引。这样整个序列始终是杂乱的，无法很好地维护。

这种方法其实是将整个序列看做是一个“块”，这个“块”太大了，才无法有效管理。

可以对序列先根据重量 $m$ 升序排序，再分块，每个块中再按距离 $r$ 升序排序。这样，每个块之间可以保证 $m$ 是递增的，块内保证 $r$ 是递增的。有了一定的规律，才有更好的维护方法。

当用某块磁石吸引时，可以找到一个 $k$ ，使得前 $k-1$ 个分块的磁石重量都可以被吸引， $k+1$ 之后的分块中，磁石的重量都无法被吸引。
对于前 $k-1$ 块，每个块内从小到大扫描，若距离也可以被吸引，那么就把这个磁石 $j$ 加入队列，同时把该分块的左端点设为j+1。这些已扫描过的磁石之后不会再重复计算。
对于第 $k$ 个分块，暴力维护，从左到右扫描每个磁石，判断是否加入队列，若加入，则 $vis$ 数组记录已访问。

用这种分块做法，只需要暴力维护大小为 $\sqrt{n}$ 的区间。

#include<bits/stdc++.h>
using namespace std;
const int N=2.5e5+10;
int x,y,p,r,n,t,L[N],R[N],maxM[N],vis[N],cnt;
struct P{int x,y,m,p,r;long long R;}a[N];
queue<tuple<int,int,int,int,int>> que;bool cmp2(P a,P b){ return a.R<b.R; }bool cmp1(P a,P b){ return a.m<b.m; }int main(){scanf("%d%d%d%d%d",&x,&y,&p,&r,&n);for(int i=1;i<=n;i++){scanf("%d%d%d%d%d",&a[i].x,&a[i].y,&a[i].m,&a[i].p,&a[i].r);a[i].R=1LL*(a[i].x-x)*(a[i].x-x)+1LL*(a[i].y-y)*(a[i].y-y);}t=sqrt(n);for(int i=1;i<=t;i++){L[i]=(i-1)*t+1;R[i]=i*t;}if(R[t]<n)  t++,L[t]=R[t-1]+1,R[t]=n;sort(a+1,a+n+1,cmp1);for(int i=1;i<=t;i++){maxM[i]=a[R[i]].m;sort(a+L[i],a+R[i]+1,cmp2);}que.emplace(x,y,0,p,r);while(que.size()){auto [x,y,m,p,r]=que.front();   que.pop();for(int i=1;i<=t;i++){if(maxM[i]<=p){for(int j=L[i];j<=R[i];j++){if(vis[j]==1){  L[i]=j;continue;    }if(a[j].R<=1LL*r*r)que.emplace(a[j].x,a[j].y,a[j].m,a[j].p,a[j].r),vis[j]=1,L[i]=j+1,cnt++;else    break;}}else{for(int j=L[i];j<=R[i];j++)if(a[j].m<=p&&a[j].R<=1LL*r*r&&vis[j]==0)que.emplace(a[j].x,a[j].y,a[j].m,a[j].p,a[j].r),vis[j]=1,cnt++;break;}}}printf("%d\n",cnt);
}