题目描述

难度分:$2200$

输入$n(1 \leq n \leq 10^5)$、$k(0 \leq k \leq 20)$和$n$个机器人的属性。

每个机器人都有三个属性：$x$、$r$、$q$，值都在$[0,10^9]$中。

$x$表示机器人在一维数轴上的位置，$q$表示机器人的智商。机器人可以与位置在$[x-r,x+r]$中的，智商在$[q-k,q+k]$中的其他机器人交流。

能够【互相】交流的机器人有多少对？

输入样例

3 2
3 6 1
7 3 10
10 5 8

输出样例

1

算法

二维数点

先将所有机器人$robots$按照$r$从大到小排序，这样从前往后遍历时，如果当前机器人可以看到前面的某个机器人，那么那个机器人也可以看到当前机器人，因为他的半径更大。

构建一个映射$q2x$“智商$\rightarrow$该智商所有机器人的位置”，每个智商的机器人位置都从小到大排好序。然后遍历$robots$数组，对于某个机器人$(x,r,q)$，就相当于求矩形$[q-k,q+k] \times [x-r,x+r]$内点的数目，即二维数点问题。对每个$q$都构建一个长度为$sz$的树状数组（$sz$为这个智商的机器人数目），本题中$k$的数量比较小，直接枚举$IQ \in [q-k,q+k]$，只要$IQ$对应的树状数组存在，就在$[x-r,x+r]$上求点的数目累加到答案上。然后把当前机器人累加到$q$对应树状数组的$x$位置上，供后续的机器人计算答案时使用。

复杂度分析

时间复杂度

将所有机器人按照$r$降序排列时间复杂度为$O(nlog_2n)$；预处理出$q2x$映射，树状数组$trees$的时间复杂度为$O(n)$；遍历所有机器人计算答案的时间复杂度为$O(nklog_2n)$，其中遍历机器人时间复杂度为$O(n)$，每个机器人遍历智商范围时间复杂度为$O(k)$，机器人和智商固定之后还要对树状数组进行区间查询操作和单点加操作，时间复杂度为$O(log_2n)$。

因此，整个算法的时间复杂度为$O(nklog_2n)$。

空间复杂度

映射$q2x$存了所有机器人的位置和智商，空间复杂度是线性的。树状数组也类似，每个智商的所有机器人位置都存在了这个树状数组中。因此，整个算法的额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 100010;
int n, k;

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

struct Robot{
    int x, r, q;
    bool operator<(const Robot other) const {
        return r > other.r;
    }
} robots[N];

int main() {
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; i++) {
        scanf("%d%d%d", &robots[i].x, &robots[i].r, &robots[i].q);
    }
    sort(robots + 1, robots + n + 1);
    unordered_map<int, vector<int>> q2x;
    for(int i = 1; i <= n; i++) {
        q2x[robots[i].q].push_back(robots[i].x);
    }
    unordered_map<int, vector<int>, custom_hash> trees;
    for(auto&[iq, pos]: q2x) {
        sort(pos.begin(), pos.end());
        int sz = pos.size();
        trees[iq] = vector<int>(sz + 1);
    }
    function<LL(int, int)> query = [&](int iq, int x) {
        auto &t = trees[iq];
        auto &pos = q2x[iq];
        LL res = 0;
        for(int i = lower_bound(pos.begin(), pos.end(), x) - pos.begin(); i > 0; i &= i - 1) {
            res += t[i];
        }
        return res;
    };
    function<void(int, int)> add = [&](int iq, int x) {
        auto &t = trees[iq];
        auto &pos = q2x[iq];
        for(int i = lower_bound(pos.begin(), pos.end(), x) - pos.begin() + 1; i < t.size(); i += i&-i) {
            t[i]++;
        }
    };
    LL ans = 0;
    for(int i = 1; i <= n; i++) {
        int q = robots[i].q, x = robots[i].x, r = robots[i].r;
        int lx = x - r, rx = x + r;
        for(int iq = q - k; iq <= q + k; iq++) {
            if(!q2x.count(iq)) continue;
            auto &pos = q2x[iq];
            ans += query(iq, rx + 1) - query(iq, lx);
        }
        add(q, x);
    }
    printf("%lld\n", ans);
    return 0;
}