题目链接：250. 磁力块

算法分析

先按照质量排序，然后分块，在每块内再按照距离排序。每块大小$\sqrt{n}$。计算出一个k，满足[1,k]块内的每个磁石的质量都小于等于队头的磁石的磁力。最坏的情况下，会换$n$次磁石，总共会有$n$块磁石入队，因此均摊时间复杂度是O(1)，暴力计算第$k+1$块的时候，复杂度是$O(\sqrt{n})$。因此，总复杂度是$O(n\ast \sqrt{n})$。

在计算$k$的时候，可以优化。存下每块内磁石的最大质量，因为之前是排序的，因此这个数据是有序的，可以二分查找出这个k。同样地，在每块内部计算距离小于队头半径的磁石时，也可以二分，但此题时间宽裕，两个二分都不用也能过。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
#define ll long long 
const int N = 250010;
struct Stone
{ll x, y, m, p, r;ll bl;double dis;
}st[N];
ll n, xx, yy, pl, rl;
int blo, ans;
int vis[N];
struct kuai
{ll maxm, l;
}b[550];
queue<Stone> q;
inline ll re()
{ll x = 0, f = 1; char c = getchar();while (c < '0' || c > '9'){if (c == '-') f= -1; c = getchar();}while (c >= '0' && c <= '9'){x = x * 10 + c - '0'; c = getchar();}return x * f; 
}
bool cmp(Stone a, Stone b)
{return a.m < b.m;
}
bool cmp1(Stone a, Stone b)
{if (a.bl == b.bl) return a.dis < b.dis;else return a.bl < b.bl;
}
bool chk(int mid, int p)
{return b[mid].maxm <= p;
}
int szfind(int p)  // 在所有块中查找小于等于p的最大值  
{int l = 0, r = st[n].bl;while (l < r){int mid = (l + r + 1) >> 1;if (chk(mid, p)) l = mid; else r = mid - 1;}return l;
}
int main()
{xx = re(); yy = re(); pl = re(); rl = re(); n = re();for (int i = 1; i <= n; ++i){st[i].x = re(); st[i].y = re(); st[i].m = re(); st[i].p = re(); st[i].r = re();st[i].dis = sqrt((st[i].x - xx) * (st[i].x - xx) + (st[i].y - yy) * (st[i].y - yy));}blo = sqrt(n);sort(st + 1, st + n + 1, cmp);  // 按质量由小到大排序  for (int i = 1; i <= n; ++i) st[i].bl = (i - 1) / blo + 1;for (int i = 1; i <= st[n].bl - 1; ++i){b[i].l = (i - 1) * blo +1; // 记录每块的最左边的位置  b[i].maxm = st[i*blo].m;  // 记录每块的最大质量  }b[st[n].bl].l = (st[n].bl - 1) * blo + 1;b[st[n].bl].maxm = st[n].m;sort(st + 1, st + n + 1, cmp1); // 同一块内按距离由小到大排序  Stone tem;tem.x = xx; tem.y = yy; tem.p = pl; tem.r = rl;q.push(tem);while (!q.empty()){Stone u = q.front(); q.pop();	int k = szfind(u.p); // [1,k]块都是最大质量小于等于u.p的 for (int t = 1; t <= k; ++t){int j;for (j = b[t].l; j <= min((ll)t * blo, n); ++j)if (st[j].dis <= u.r){if (!vis[j]){++ans; q.push(st[j]); vis[j] = 1;}					}else break;b[t].l = j;}// 暴力计算第k+1个块 if (k != st[n].bl)  // 需要判断k是否是最后一个块  {int j;for (j = b[k+1].l; j <= min((ll)(k + 1) * blo, n); ++j)if (st[j].dis <= u.r){if (st[j].m <= u.p && !vis[j]){++ans; q.push(st[j]); vis[j] = 1;}}else break;}		}printf("%d\n", ans);return 0;
}

总结与反思

1. 此题细节很多。在二分查找k时，要将左端点$l$置为0，如果k为0的话，可以正确取值，否则不能正确取值。在暴力计算第$k+1$块时，要判断$k$是否是最后一块，如果是最后一块，就不能在计算第$k+1$块了，否则又要错误。光debug这个错误，用了将近一天的时间。

2. 数据设定为long long了，但是快读的时候忘开long long。

3. 代码可以再精简的，比如存下$L[i]$和$R[i]$，作为每块的左右端点，更清晰些；在入队列的时候，可以让下标$i$入队列，不用整个结构体$st[i]$都入。