磁力块[分块]

Solution

$O(N^2)$ 暴力自然不用说, 用手中石子去检查地上石子是否捡的起来, 若捡的起来就捡, 直到没有石子可以捡为止

正解: 分块

对于这种有多个属性的若干物品需要比较大小来检查合法不合法的问题,
可以尝试这个方法:

1. 整个数组排序
2. 分块
3. 块内排序
~~4. 暴力~~

于是先将地上石子按距离排序
分成 $sqrt{N}$ 个块, 每个块内按质量排序
此时手中就有了 处理过后的整个数组, 每个块的包含的极值 (由于对每个小块排序乱了距离的单调性, 质量单调性得到保证, 于是极值只需要记距离即可)
每次拿手中的石子将所有能捡到的石子全部捡起 (即加入队列),
将手中石子弹出队列, 取出队首继续进行上述操作, 直到队列为空

接下来详细叙述石头怎么捡

先找到第一个最小距离小于该手中石头吸引半径的块, 对于这个块前面的所有块, 其中符合条件的石子可能就在这些块中

对每个可能的块遍历 (可以在上述找的过程中实行), 同样找到第一个不符合条件的石子 $T$ , 这个块中符合条件的石子即 $T$ 前面所有的石子, 将这些石子从块内删除 , 加入队列

对于删除操作, 可以记每个块内左右端点为 $l, r$ , 删除时直接将 $l$ 移动到 $T$ 的位置上即可 (删除过程可以边走边删)

编码中出现的小错误

为什么这段代码会爆掉?

int &l = B[j].l, r = B[j].r;
while(l <= r && (ft.r >= A[l].d && ft.p >= A[l].m)) Q.push(A[l ++]);

而这是正确的 $↓$

if(B[j].min_d > ft.r) break ; //~
int &l = B[j].l, r = B[j].r;
if(B[j].max_d <= ft.r)
        while(l <= r && A[l].m <= ft.p){
                if(!Used[l]) Q.push(A[l]), Used[l] = 1;
                l ++;
        }
else{
        for(reg int i = B[j].l; i <= B[j].r; i ++)
                if(A[i].m <= ft.p && A[i].d <= ft.r)
                        if(!Used[i]) Q.push(A[i]), Used[i] = 1;
}

这是因为在将小区块排序后, 小区块内的距离并不是单调递增, 只有当这个块内的所有石子距离一定符合条件时, 才可以直接挪动区块的 $L$ , 即 $L ++$ (完全扔掉石子 $A_L$ )

Code

#include<bits/stdc++.h>
#define reg register

int read(){
        int s = 0, flag = 1;
        char c;
        while((c=getchar()) && !isdigit(c))
                if(c == '-'){ c = getchar(), flag = -1; break ; }
        while(isdigit(c)) s = s*10 + c-'0', c = getchar();
        return s * flag;
}

typedef long long ll;
const int maxn = 350005;

int N;
int Used[maxn];

struct Stone{
        int x, y, m, p; ll d, r;
        Stone(int x=0, int y=0, int m=0, int p=0, ll d=0, ll r=0):x(x), y(y), m(m), p(p), d(d), r(r) {}
} A[maxn];
struct Block{ int l, r; ll max_d, min_d; } B[maxn];

bool cmp_d(Stone a, Stone b){ return a.d < b.d; }
bool cmp_m(Stone a, Stone b){ return a.m==b.m?a.d<b.d:a.m<b.m; }

int main(){
        freopen("magnet.in", "r", stdin);
        freopen("magnet.out", "w", stdout);
        A[0].x = read(), A[0].y = read(), A[0].p = read(), A[0].r = read(); A[0].r *= A[0].r; A[0].d = 0;
        N = read();
        for(reg int i = 1; i <= N; i ++){
                A[i].x = read(), A[i].y = read(), A[i].m = read(), A[i].p = read(), A[i].r = read();
                A[i].r *= A[i].r;
                A[i].d = (1ll*A[i].x-A[0].x)*(A[i].x-A[0].x) + (1ll*A[i].y-A[0].y)*(A[i].y-A[0].y);
        }
        int size = sqrt(N), cnt = 0;
        std::sort(A+1, A+N+1, cmp_d);
        for(reg int i = 1; i <= N; i += size){
                B[++ cnt].l = i, B[cnt].r = std::min(N, i+size-1);
                B[cnt].min_d = A[i].d, B[cnt].max_d = A[B[cnt].r].d;
                std::sort(A+i, A+B[cnt].r+1, cmp_m);
        }
        int Ans = 0;
        std::queue <Stone> Q; Q.push(A[0]);
        while(!Q.empty()){
                Stone ft = Q.front(); Q.pop(); Ans ++;
                for(reg int j = 1; j <= cnt; j ++){
                        if(B[j].min_d > ft.r) break ; //~
                        
                        int &l = B[j].l, r = B[j].r;
                        if(B[j].max_d <= ft.r)
                                while(l <= r && A[l].m <= ft.p){
                                        if(!Used[l]) Q.push(A[l]), Used[l] = 1;
                                        l ++;
                                }
                        else{
                                for(reg int i = B[j].l; i <= B[j].r; i ++)
                                        if(A[i].m <= ft.p && A[i].d <= ft.r)
                                                if(!Used[i]) Q.push(A[i]), Used[i] = 1;
                        }
                }
        }
        printf("%d
", Ans-1);
        return 0;
}