「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;
}