[被迫营业2-1]分块解决双维度查询问题

Problem

ACWing 250 磁力块

How to solve it?

考虑BFS，先将(L)加入队列，然后每次将其能吸引的磁石加入队列(_{[1]})，最后进入过队列的数(-1)（因为答案不包含最初携带的磁石(L)）即为所求。

考虑如何找到哪些能吸引的磁石？

Solution 1 (mathcal{O(n)})

枚举每个磁石，判断其能不能被吸引。

# include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 250005;

struct node
{
    ll x,y,m,p,r;
    node() {}
    node(ll _x,ll _y,ll _m,ll _p,ll _r) : x(_x),y(_y),m(_m),p(_p),r(_r) {}
}a[N],L;

int n;

bool vis[N];

double dist(node a,node b)
{
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

bool check(node a,node b) // a xi b
{
    if(double(a.r) < dist(a,b)) return 0;
    if(b.m > a.p) return 0;
    return 1;
}

void Read(struct node &x,bool opt = 0)
{
    if(opt) // read L
    {
        scanf("%lld%lld%lld%lld",&x.x,&x.y,&x.p,&x.r);
    }
    else scanf("%lld%lld%lld%lld%lld",&x.x,&x.y,&x.m,&x.p,&x.r);
    return;
}

void bfs(void)
{
    queue <node> q;
    q.push(L);
    while(!q.empty())
    {
        node x = q.front();q.pop();
        for(int i = 1; i <= n; i++)
        {
            if(vis[i]) continue;
            if(check(x,a[i])) 
            {
                q.push(node(x.x,x.y,a[i].m,a[i].p,a[i].r));
                vis[i] = 1;
            }
        }
    }
    return;
}

int main(void)
{
    Read(L,1);
    scanf("%d",&n);
    for(int i = 1; i <= n; i++) 
    {
        Read(a[i]);
    }
    bfs();
    int total = 0;
    for(int i = 1; i <= n; i++) total += vis[i];
    printf("%d
",total);
    return 0;
}

Solution 2 (mathcal{O}(sqrt{n}))

预处理：将磁石按照质量从小到大排序，并分块，长度为(sqrt{n})。

（下文为了方便，设块长度为(len)，数量为(num)）

对于每个块，块内按照与((x_0,y_0))的距离从小到大排序。

预处理出每个块中磁石的最大质量( ext{Max-m})。

对于每次询问：

令队头磁石的磁力为(p)。

已经有一个分界值(k)，使得：

(forall1 le i le k, ext{Max-m}[i] le p).

(forall k < i le num, ext{Max-m}[i] > p)

Lemma 1. 此时能被吸引的磁石只会在([1,min(k + 1,num)])的块中。

Proof:

若(k + 1 > num)，引理显然成立。

若(k + 1 le num)：

显然此时( ext{Max-m}[k + 1] > p)，那么说明在(k + 1)块中一定有质量大于(p)的磁块，而这个磁块被分到了(k + 1)块中，说明对于任何在(k + 1)块之后的所有磁石都要大于它。那么显然是无法吸引的。证毕。

对于(1 le i le k)的块，因为块中已经按照距离排序，所以我们每次都只需要从开头开始找，若能吸引则加入队列，并从块中删除，防止重复入队。

对于块(k + 1)，暴力枚举即可。

# include <bits/stdc++.h>
using namespace std;

# define int long long

# define y0 Iakioi
# define x0 Youakioi

const int N = 250005;

int n;
int x0,y0;
int num,len;
int Left[1000],Right[1000];
int Max_m[1000];

int total = 0;

struct node
{
    int dis,m,p,r;
    node() {}
    node(int _dis,int _m,int _p,int _r) : dis(_dis),m(_m),p(_p),r(_r) {}
}a[N],L;

bool vis[N];

bool compare(const struct node &x,const struct node &y)
{
    return x.m < y.m;
}

bool compare2(const struct node &x,const struct node &y)
{
    return x.dis < y.dis;
}

void init(void)
{
    sort(a + 1, a + n + 1, compare);
    len = sqrt(n);
    num = (n - 1) / len + 1;
    for(int i = 1; i <= num; i++)
    {
        Left[i] = (i - 1) * len + 1;
        Right[i] = min(i * len,n);
        Max_m[i] = a[Right[i]].m;
        sort(a + Left[i],a + Right[i] + 1, compare2);
    }
    return;
}

void bfs(void)
{
    queue <node> q;
    q.push(L);
    while(!q.empty())
    {
        node x = q.front();q.pop();
        for(int i = 1; i <= num; i++)
        {
            if(Max_m[i] > x.p)
            {
                for(int j = Left[i]; j <= Right[i]; j++)
                {
                    if(!vis[j] && a[j].dis <= x.r && a[j].m <= x.p)
                    {
                        q.push(a[j]);
                        ++total;
                        vis[j] = 1;
                    }
                    else if(a[j].dis > x.r) break;
                }
                break;
            }
            else
            {
                while(Left[i] <= Right[i] && a[Left[i]].dis <= x.r)
                {
                    if(!vis[Left[i]])
                    {
                        q.push(a[Left[i]]);
                        ++total;
                    }
                    ++Left[i];
                }
            }
        }
    }
    return;
}

signed main(void)
{
    scanf("%lld%lld%lld%lld",&x0,&y0,&L.p,&L.r);
    L.r *= L.r;
    L.m = L.dis = 0;
    scanf("%lld",&n);
    for(int i = 1; i <= n; i++)
    {
        int x,y;
        scanf("%lld%lld%lld%lld%lld",&x,&y,&a[i].m,&a[i].p,&a[i].r);
        a[i].dis = (x - x0) * (x - x0) + (y - y0) * (y - y0);
        a[i].r *= a[i].r;
    }   
    init();
    bfs();
    printf("%lld
",total);
    return 0;
}

Solution 2 - Faster

在第(k + 1)块中，如果遇到(dis > x.r)的，可以直接break.

（上面已经写了）