「CH 46A」磁力块 (分块 + BFS)

CH 46A
题意:见上。

容易发现可以用BFS从L开始一路下去找能吸附的。
关键是怎么找能吸附的,这里有两维$(m \leq p, dis \leq r)$这里可以用平衡树之类的去维护,比较麻烦
其实可以用分块来做。将原数组按$m$排序,然后就消除第一维影响
然后在块中按$dis$重新排序,然后就能满足块中$dis$单调,对于看作整体的块$m$单调。(分块处理二维的问题)
那么我们只需要查询,对于每个$m \leq p$整块,找$dis \leq r$的元素并且标记到当前位置,之后扫描从这里开始(前面都被挖走了)。对于$m$不完全小于$p$的一个不完整块,暴力统计。

这里分块可以简单写:$l,r$表示当前块的开始结束位置,不需要$bl$数组,询问也可以插到 BFS 里写。

知识点:
1、注意分块中能不用 stl 就不用,并且查询可以合并到主程序写
2、 分块处理二维的问题

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const int MAXN = 250000 + 5;
struct data {
int x, y, m, p;
LL r, dis;
}pnt[MAXN];
struct node {int p; LL r;};
int tot, x0, y0, pL, rL, n, blolen, maxm[MAXN], vis[MAXN], l[MAXN], r[MAXN];
queue<node > q;
bool cmp_m(data a, data b) {return a.m < b.m;}
bool cmp_d(data a, data b) {return a.dis < b.dis;}
void clean() {
tot = 0, ms(maxm, 0), ms(vis, 0);
}
int solve() {
clean();
scanf("%d%d%d%d%d", &x0, &y0, &pL, &rL, &n);
blolen = (int)sqrt(n);
for (int i = 1; i <= n; ++i) {
scanf("%d%d%d%d%lld", &pnt[i].x, &pnt[i].y, &pnt[i].m, &pnt[i].p, &pnt[i].r);
pnt[i].r *= pnt[i].r, pnt[i].dis = 1ll * (pnt[i].x - x0) * (pnt[i].x - x0) + 1ll * (pnt[i].y - y0) * (pnt[i].y - y0);
}
sort(pnt + 1, pnt + 1 + n, cmp_m);
for (int i = 1; i <= n; i += blolen) {
l[++tot] = i, r[tot] = min(i + blolen - 1, n);
maxm[tot] = pnt[r[tot]].m;
sort(pnt + l[tot], pnt + 1 + r[tot], cmp_d);
}
q.push((node){pL, 1ll * rL * rL});
int ans = -1;
while (!q.empty()) {
node p = q.front(); q.pop();
++ans;
int i;
for (i = 1; i <= tot; ++i) {
if (maxm[i] > p.p) {
for (int j = l[i]; j <= r[i]; ++j) {
if (!vis[j] && pnt[j].dis <= p.r && pnt[j].m <= p.p) vis[j] = 1, q.push((node){pnt[j].p, pnt[j].r});
}
break ;
} else {
while (l[i] <= r[i]) {
if (pnt[l[i]].dis <= p.r) {
if (!vis[l[i]]) q.push((node){pnt[l[i]].p, pnt[l[i]].r});
} else break ;
++l[i];
}
}
}
}
printf("%d\n", ans);
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}

------ 本文结束 ------