在一片广袤无垠的原野上，散落着N块磁石。
每个磁石的性质可以用一个五元组(x,y,m,p,r)描述，其中x,y表示其坐标，m是磁石的质量，p是磁力，r是吸引半径。
若磁石A与磁石B的距离不大于磁石A的吸引半径，并且磁石B的质量不大于磁石A的磁力，那么A可以吸引B。
小取酒带着一块自己的磁石L来到了这片原野的(x0,y0)(x0,y0)处，我们可以视磁石L的坐标为(x0,y0)(x0,y0)。
小取酒手持磁石L并保持原地不动，所有可以被L吸引的磁石将会被吸引过来。
在每个时刻，他可以选择更换任意一块自己已经获得的磁石（当然也可以是自己最初携带的L磁石）在(x0,y0)(x0,y0)处吸引更多的磁石。
小取酒想知道，他最多能获得多少块磁石呢？
第一行五个整数x0,y0,pL,rL,Nx0,y0,pL,rL,N，表示小取酒所在的位置，磁石L磁力、吸引半径和原野上散落磁石的个数。
接下来N行每行五个整数x,y,m,p,r，描述一块磁石的性质。
输出一个整数，表示最多可以获得的散落磁石个数（不包含最初携带的磁石L）。
1≤N≤2500001≤N≤250000,
−109≤x,y≤109−109≤x,y≤109,
1≤m,p,r≤1091≤m,p,r≤109
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
蓝书解释的很清楚了，及时维护块的左端点很巧妙。注释里有详解。
#include <bits/stdc++.h> #define SIZE 250005 using namespace std; int x0, y00, pl, rl, N, ans = 0; int L[SIZE], R[SIZE], pos[SIZE], t; bool vis[SIZE] = {0}; struct Stone{ int x, y, m, p, r; double dis;//距离 } s[SIZE]; double calc(Stone a, Stone b){ return sqrt(1ll * (a.x - b.x) * (a.x - b.x) + 1ll * (a.y - b. y) * (a.y - b.y)); } bool cmp1(Stone a, Stone b){ return a.m < b.m; } bool cmp2(Stone a, Stone b){ return a.dis < b.dis; } queue<Stone> q; void BFS(){ int m = 0; q.push(Stone{x0, y00, m, pl, rl}); while(q.size()){ Stone temp = q.front(); q.pop(); for(int i = 1; i <= t; i++){//遍历块 int cnt = 0, j;//cnt为当前块内质量大于当前手持磁石引力的数目 for(j = L[i]; j <= R[i]; j++){//遍历块内 if(s[j].m > temp.p) cnt++;//通过cnt变量来判断当前块内磁石质量是否全部小于手持磁石引力，以此来确定是否是“边角块 ” else{ if(s[j].dis <= 1ll * temp.r){//首先判断距离 if(!vis[j]){//其次判断是否访问过。因为对于某次循环的“边角块”而言，其含有的磁石可能已经入队，但区间端点并未改变，因此要额外判定 ans++; vis[j] = 1; q.push(s[j]); } } else break;//因为块内已经按距离排序了，大于的话直接结束当前块的循环 } } if(!cnt) L[i] = j;//质量全部小于的时候（说明当前块非边角块）才更新端点 else break;//当前块内有质量大于手持磁石引力的磁石了，说明为边角块，直接结束循环 } } } int main(){ cin >> x0 >> y00 >> pl >> rl >> N; for(int i = 1; i <= N; i++) { scanf("%d%d%d%d%d", &s[i].x, &s[i].y, &s[i].m, &s[i].p, &s[i].r); s[i].dis = calc(s[i], Stone{x0, y00, 0, 0, 0}); } sort(s + 1, s + N + 1, cmp1);//整体按照质量排序 //常规分块预处理 t = sqrt(N); for(int i = 1; i <= t; i++){ L[i] = (i - 1) * sqrt(N) + 1; R[i] = i * sqrt(N); } if(R[t] < N) t++, L[t] = R[t - 1] + 1, R[t] = N; for(int i = 1; i <= t; i++){ for(int j = L[i]; j <= R[i]; j++){ pos[j] = i; } } for(int i = 1; i <= t; i++){ sort(s + L[i], s + R[i] + 1, cmp2);//块内按照距离排序 } BFS(); cout << ans; }
原文：https://www.cnblogs.com/lipoicyclic/p/13311433.html