CF198E Gripping Story 题解

题意：

Qwerty 的船在位置 $(x, y)$，船上有一个机械臂，其力量为 $p$，长度为 $r$，即可以拿到质量不超过 $p$，距离不超过 $r$ 的物品。

有 $n$ 个机械臂散落在平面内，第 $i$ 个机械臂在位置 $(x_i, y_i)$，其质量、力量和长度分别为 $m_i,p_i,r_i $。

Qwerty 不能移动他的船，但他拿到某个机械臂后可以将其安装到船上使用，问他最多能获得多少机械臂。

输入格式：

第一行 $x,y,p,r,n$ ，接下来 $n$ 行 $x_i,y_i,m_i,p_i,r_i$

输出格式：

一行，即答案。

数据范围：

$1\le n \le 2.5\times 10^5,~-10^9 \le x,y,x_i,y_i \le10^9,~1\le p,r,m_i,p_i,r_i\le 10^9$

如果机械臂 $i$ 能够帮助拿到 $j$ ，那么认为 $i$ 到 $j$ 有一条有向边

可以发现最终答案就是计算整张图的可达性，然而本题不能直接暴力建出图。

当然「不能暴力建出图」不等于「不能用其他方式模拟图」。

因为仅当 $m_i \le p$ 且 $d_i \le r$ 时，机械臂才能被拿走，这是一个二维偏序问题。

所以我们不妨把 $d_i$ 从小到大排序，此时我们需要做的是维护在 $d_i$ 的一定范围内，其满足条件的 $m_i$ 的情况

可以发现 $m_i$ 通过有序数据结构可以很好维护，我们每次只需取出所有满足条件的 $m_i$ 即可。

而 $d_i$ 因为过于离散——没错，我们可以离散化，从而用线段树维护。

每个线段树上的节点维护当前区间内的 $m_i$ 最小值，显然这对于修改需要非常多次的操作

于是我们考虑以单调栈维护 $m_i$ ，这样每次只需要 pop() 一下即可（代码里用的是 vector 模拟栈）

可能讲的不是很细，具体的 bfs 过程就看代码吧。另外这个单调栈实际上只出不进，是不影响复杂度的

时间复杂度 $\mathcal{O}(n\log n)$ ，空间复杂度 $\mathcal{O}(n \log n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
typedef pair<int,int> pii;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
namespace FastIO
{
    #define gc() readchar()
    #define pc(a) putchar(a)
    #define SIZ (int)(1e6 + 15)
    char buf1[SIZ], *p1, *p2;
    char readchar()
    {
        if(p1 == p2){ p1 = buf1,p2 = buf1 + fread(buf1, 1, SIZ, stdin); }
        return p1 == p2? EOF : *p1++;
    }
    template<typename T>void read(T &k)
    {
        char ch = gc(); T x = 0, f = 1;
        while(!isdigit(ch)){ if(ch == '-'){ f = -1; }ch = gc(); }
        while(isdigit(ch)){ x = (x << 1) + (x << 3) + (ch ^ 48); ch = gc(); }
        k = x * f;
    }
    template<typename A, typename ...B>
        void read(A &x, B &...y) { return read(x), read(y...); }
    template<typename T>void write(T k)
    {
        if(k < 0){ k = -k; pc('-'); }
        static T stk[66]; T top = 0;
        do{ stk[top++] = k % 10, k /= 10; } while(k);
        while(top) { pc(stk[--top] + '0'); }
    }
}using namespace FastIO;
#define sq(x) ((x) * (x))
#define ls(at) ((at) << 1)
#define rs(at) ((at) << 1 | 1)
#define N ((int)(2.5e5 + 15))

int n, o[N]; char used[N];
vector<int> tr[N * 4]; queue<pii> q;
struct node { int d, m, p, r; } a[N];
bool operator<(node a, node b) { return a.d < b.d; }
void insert(int x, int at = 1, int l = 1, int r = n)
{
    tr[at].push_back(x);
    if(l == r) return; int mid = (l + r) >> 1;
    if(mid >= x) insert(x, ls(at), l, mid);
    else insert(x, rs(at), mid + 1, r);
}
int query(int x, int w, int at = 1, int l = 1, int r = n)
{
    if(l > x) return 0;
    while(!tr[at].empty() && used[tr[at].back()]) tr[at].pop_back();
    if(tr[at].empty() || a[tr[at].back()].m > w) return 0;
    if(r <= x) return tr[at].back(); int mid = (l + r) >> 1;
    int tmp = query(x, w, ls(at), l, mid); if(tmp) return tmp;
    return mid < x ? query(x, w, rs(at), mid + 1, r) : 0;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int sx, sy, sp, sr; read(sx, sy, sp, sr, n);
    for(int i = 1; i <= n; i++)
    {
        int x, y, m, p, r; read(x, y, m, p, r); 
        a[i] = {sq(x - sx) + sq(y - sy), m, p, r};
    }
    sort(a + 1, a + 1 + n);
    for(int i = 1; i <= n; i++) o[i] = i;
    sort(o + 1, o + 1 + n, [](int x, int y) { return a[x].m > a[y].m; });
    for(int i = 1; i <= n; i++) insert(o[i]);
    q.push({sp, sr}); int res = 0;
    while(!q.empty())
    {
        auto [p, r] = q.front(); q.pop(); int x;
        r = upper_bound(a + 1, a + 1 + n, (node){sq(r), 0, 0, 0}) - a - 1;
        while(x = query(r, p)) {
            used[x] = true; ++res; q.push({a[x].p, a[x].r});
        }
    }
    write(res); pc('\n');
    return 0;
}