题解：CF198E Gripping Story

· · 题解

没有人用分块做法？我来交一篇。

首先考虑暴力做法，初始只有一个机械臂，我们暴力的把所有能抓过来的机械臂都抓过来，再分别尝试抓过来的机械臂。

这显然是一个 bfs 的过程，复杂度为 O(n ^ 2)，无法通过题目。

分块本身就是一个优雅的暴力，所以我们考虑本题使用分块优化。

不妨先取块长为 \sqrt{n}。

我们接下来分析：暴力有什么问题？

我们发现，暴力法每次都要把所有机械臂遍历一遍，无论其是否被抓走，这导致很多已经被抓走的机械臂被重复遍历了很多次，考虑从这个角度优化。

可以发现这么一个性质：设第 i 个机械臂到 (x,y) 的距离为 dis_i，如果 dis 和 m 都是单调不减的，我们显然可以维护一个指针，每次向右移动指针抓取机械臂直到不能抓为止。

在本例中，指针是不用向左移的，即每个机械臂都只会遍历一次，所以总复杂度是 O(n) 的。

但出题人会这么良心吗？不会的！

不过，这给我们一个启发：我们可以让每个块内都有类似的性质，即我们对每个块维护一个上例中的指针，使这个指针不用左移。

上例中 dis 和 m 是严格单调的，但是我们无法通过排序使 dis 和 m 都单调。

本题关键来了：

我们可以通过“整体” m 单调，“块内” dis 单调！

形式化来讲，记 belong_i 为第 i 个机械臂所在块的编号，对于任意 i < j，若 belong_i < belong_j，则 m_i \leq m_j；若 belong_i = belong_j，则 dis_i \leq dis_j。

这个思路巧妙在哪？

分块遵循的都是整体维护，块内暴力原则，那本题中的整体是什么？

很显然，有了整体的 m 单调，我们可以确定我们需要查询哪些块，不查询哪些块。

具体来说，我们可以对每个块维护一个 Max 表示最重的机械臂重量。我们从左往右暴力查找（也可以二分，但只起到优化常数的效果），当查找到第一个 Max_k > p 时，说明 1 \sim k - 1 块中所有机械臂的 m 都满足要求，第 k + 1 \sim n 块中所有机械臂的 m 都不满足要求，第 k 块无法确定，需要暴力 O(\sqrt{n}) 查询。

对于前 k - 1 块，就可以用上述移动指针的方式查询，每个块均摊是 O(1) 的，所以这部分查询复杂度也是 O(\sqrt{n}) 的。

综上，我们得到了一个 O(n\sqrt{n}) 的算法。

很奇怪的是我的代码中常量 N 的大小需要比题目中的 n 开大 4 倍，否则会 RE，有大佬可以解释的欢迎留言！

#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
typedef long long ll;
const int N = 1e6 + 9,SqrtN = 1e6 + 9;
int n;
struct Data{
    int x,y,m,p;
    ll r,dis;//dis存的是真实距离的平方，所以将读入的 r 也全部平方
} a[N];
struct block{//存储块的结构体
    int l,r;//块的左右边界，注意本代码中直接将 l 当作文中提到的指针使用
} b[SqrtN];
int belong[N];
int block_cnt,block_len;
int Max[SqrtN];
bool vis[N];
ll sq(int k){
    return (ll)k * k;
}
ll dist(Data m1,Data m2){
    int x1 = m1.x,y1 = m1.y,x2 = m2.x,y2 = m2.y;
    return sq(x1 - x2) + sq(y1 - y2);
}
bool cmp1(Data m1,Data m2){
    return m1.m < m2.m;
}
bool cmp2(Data m1,Data m2){
    return m1.dis < m2.dis;
}
void block_sort(int block_id){//块内按dis排序
    int l = b[block_id].l,r = b[block_id].r;
    sort(a + l,a + r + 1,cmp2);
}
void build_block(){
    block_cnt = block_len = (int)sqrt(n);
    for(int i = 1;i <= block_cnt;i++){
        b[i].l = b[i - 1].r + 1;
        b[i].r = block_len * i;
    }
    b[block_cnt].r = n;
    for(int i = 1;i <= block_cnt;i++){
        block_sort(i);
        for(int j = b[i].l;j <= b[i].r;j++){
            Max[i] = max(Max[i],a[j].m);
            belong[j] = i;
        }
    }
}
queue<Data>q;
int ans;
void attract(Data u){
    int pos = n + 1;
    for(int i = 1;i <= block_cnt;i++)
        if(Max[i] > u.p){
            pos = i;
            break;
        }
    for(int i = 1;i <= pos - 1;i++){
        while(b[i].l <= b[i].r && dist(a[0],a[b[i].l]) <= u.r){
            int j = b[i].l;
            if(!vis[j]){            
                ans++;
                q.push(a[j]);
                vis[j] = true;//这个加不加无所谓
            }
            b[i].l++;//移动指针
        }
    }
    if(pos == n + 1)
        return;
    for(int i = b[pos].l;i <= b[pos].r;i++)
        if(a[i].m <= u.p && dist(a[0],a[i]) <= u.r && !vis[i]){
            ans++;
            vis[i] = true;//暴力取走的必须标记，否则可能会在移动指针时被重复计算
            q.push(a[i]);
        }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin >> a[0].x >> a[0].y >> a[0].p >> a[0].r >> n;
    for(int i = 1;i <= n;i++)
        cin >> a[i].x >> a[i].y >> a[i].m >> a[i].p >> a[i].r;
    for(int i = 0;i <= n;i++){
        a[i].r = sq(a[i].r);
        a[i].dis = dist(a[0],a[i]);
    }
    sort(a + 1,a + n + 1,cmp1);//整体满足m单调
    build_block();
    vis[0] = true;
    q.push(a[0]);
    while(!q.empty() && ans < n){
        Data u = q.front();
        q.pop();
        attract(u);
    }
    cout << ans;
    return 0;
}