题解 | 算法竞赛进阶指南 磁力块

思路

一种简单的思路就是不断地将可以够到的磁力块进队列,并且将未进队列,但是队首磁石能够到磁石全部进队列.
这样主要的复杂度就在于寻找磁石可以够到的磁石.如果暴力找的话复杂度就退化成了.
用线段树等数据结构来维护似乎并不怎么可靠.所以就要用可愛い 分块啦qwq.
按照每个磁石与的距离排序并分为个块,每个块内分别按照磁力排序.每个块维护一个指针,每块第一个元素至都已经进队过.
每次用磁石吸引其他磁石时,对于所有所包含磁石距都不大于的半径的块,直接移动,将质量不大于的磁力的磁石全部吸引过来.剩下的可以吸引过来的磁石肯定在后面一个不完整的块,暴力枚举所有磁石并打上标记即可.前面进行的吸引时别忘了把打过标记的跳过去.
完整的块只有个,总复杂度为,所有指针总共移动了,不完整的块每次吸引需要的复杂度,因此总复杂度还是.

代码

#include<bits/stdc++.h>
using namespace std;
#define i64 long long
#define MAXN 250005
#define fp( i, b, e ) for ( int i(b), I(e); i <= I; ++i )
#define fd( i, b, e ) for ( int i(b), I(e); i >= I; --i )
#define go( i, b ) for ( int i(b), v(to[i]); i; v = to[i = nxt[i]] )
template<typename T> inline void cmax( T &x, T y ){ x < y ? x = y : x; }
template<typename T> inline void cmin( T &x, T y ){ y < x ? x = y : x; }
#define getchar() ( p1 == p2 && ( p1 = bf, p2 = bf + fread( bf, 1, 1 << 21, stdin ), p1 == p2 ) ? EOF : *p1++ )
char bf[1 << 21], *p1(bf), *p2(bf);
template<typename T>
inline void read( T &x ){ char t(getchar()), flg(0); x = 0;
    for ( ; !isdigit(t); t = getchar() ) flg = t == '-';
    for ( ; isdigit(t); t = getchar() ) x = x * 10 + ( t & 15 );
    flg ? x = -x : x;
}

#if _WIN64 
template<typename ...Args>
inline void err( Args ...args ){
    fprintf( stderr, args... );
}
#else
void err(...){}
#endif

clock_t t_bg, t_ed;

int P, N, B; i64 R, X, Y, x, y;
inline i64 sqr( i64 x ){ return x * x; }
struct node{
    int m, p; i64 r, d;
    bool operator < ( const node &t )const{ return d < t.d; }
}a[MAXN]; i64 b[MAXN];
bool cmp( node x, node y ){ return x.m < y.m; }
bool vs[MAXN]; int p[505], e[505], ans;
queue<int> Q;

int main(){
    t_bg = clock();
    read(X), read(Y), read(a[0].p), read(a[0].r), read(N), a[0].r = sqr(a[0].r);
    fp( i, 1, N ) b[i] = i, read(x), read(y), a[i].d = sqr(x - X) + sqr(y - Y),
        read(a[i].m), read(a[i].p), read(a[i].r), a[i].r = sqr(a[i].r);
    sort( a + 1, a + N + 1 ), B = sqrt(N);
    fp( i, 1, N ) b[i] = a[i].d;
    fp( i, 0, (N - 1) / B ) e[i] = p[i + 1] = i * B + 1,
        sort(a + i * B + 1, a + min((i + 1) * B, N ) + 1, cmp);
    e[(N - 1) / B + 1] = N + 1;
    Q.push(0);
    while( !Q.empty() ){
        int c(Q.front()), u; ++ans, Q.pop();
        u = upper_bound( b + 1, b + N + 1, a[c].r ) - b;
        if ( b[u] != a[c].r ) --u;
        fp( i, (u - 1) / B * B + 1, min( ( (u - 1) / B + 1 ) * B, N ) )
            if ( a[c].r >= a[i].d && a[c].p >= a[i].m && !vs[i] )
                vs[i] = 1, Q.push(i);
        fp( i, 1, (u - 1) / B )
            for ( ; p[i] < e[i] && a[c].p >= a[p[i]].m; ++p[i] )
                if ( !vs[p[i]] ) vs[p[i]] = 1, Q.push(p[i]);
    } printf( "%d\n", ans - 1 );
    t_ed = clock();
    err( "\n========info========\ntime : %.3f\n====================\n", (double)( t_ed - t_bg ) / CLOCKS_PER_SEC );
    return 0;
}