【题解】CF1045G AI Robots

· · 题解

原题链接

本蒟蒻不会cdq分治qwq，写一个不同的解法。

解题思路

首先将问题转化为，对于每一个机器人，有多少个机器人可以和它对话。

然后这里有两个限制条件：智商 q_i-K\le q_j\le q_i+K，位置 x_i-r_i\le x_j\le x_i+r_i，这似乎是树套树的模板题。然而：

Since they are intelligent robots, some of them will talk if they see each other.

这要求两个机器人可以互相看到，那树套树就有些麻烦了，同时也会轻易超出本题小的可怜的250MB内存限制。

我们根据 r_i 从大到小对所有机器人进行排序，然后我们让排在后面的数排在前面的。这样做有两个用处：

  1. 如果视野小的能看到视野大的，那么视野大的一定看得到视野小的，解决了互相看到的问题；
  2. 可以防止出现十分恶心的数重数漏的问题。

现在我们只剩下了位置和智商两个限制条件。可以写树套树但是空间会炸。

其实题面给了一个非常好的东西 K\le20。这意味着对于第 i 个机器人，我们完全可以枚举 [q_i-K,q_i+K]。开一个map记录每一个智商对应的权值线段树，我们就可以完美地切掉这题了。

代码实现

#include <bits/stdc++.h>
using namespace std;
int n,k,maxx;
set<int> num;
map<int,int> no;
struct TreeNode
{
    int val;
    TreeNode *lc,*rc;
    TreeNode(): val(0)
        { lc=rc=nullptr; }
};
typedef TreeNode *pNode;
void modify(int p,pNode &i,int l=1,int r=maxx)
{
    if(!i)  i=new TreeNode;
    i->val++;
    if(l!=r)
    {
        int mid=(l+r)>>1;
        if(mid>=p)  modify(p,i->lc,l,mid);
        else    modify(p,i->rc,mid+1,r);
    }
}
int query(int lq,int rq,pNode i,int l=1,int r=maxx)
{
    if(!i)  return 0;
    if(l>=lq && r<=rq)  return i->val;
    int mid=(l+r)>>1,res=0;
    if(mid>=lq) res+=query(lq,rq,i->lc,l,mid);
    if(mid<rq)  res+=query(lq,rq,i->rc,mid+1,r);
    return res;
}
map<int,pNode> t;
struct Robot
{
    int x,r,q;
    inline bool operator <(const Robot &b)const
        { return r>b.r; }
}a[100005];
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d%d",&a[i].x,&a[i].r,&a[i].q);
        num.insert(a[i].x);
        num.insert(a[i].x+a[i].r);
        num.insert(a[i].x-a[i].r);
    }
    for(int i: num) no[i]=++maxx;
    sort(a+1,a+n+1);
    long long ans=0;
    for(int i=1;i<=n;i++)
    {
        int x=no[a[i].x],lb=no[a[i].x-a[i].r],rb=no[a[i].x+a[i].r];
        for(int j=a[i].q-k;j<=a[i].q+k;j++)
        {
            auto tj=t.find(j);
            if(tj!=t.end())
                ans+=query(lb,rb,tj->second);
        }
        modify(x,t[a[i].q]);
    }
    printf("%lld",ans);
    return 0;
}