题解 CF1045G 【AI robots】

· · 题解

zz的布星啊……经rqy指点一番才做了这题

rqy是我们的红太阳,没有他我们就会死

本题题解

既然有翻译了我就不再重新复述题意了

那么我们来看既然一对机器人只会被数一次，那么我们就有三种选择了

1.让智商高的数智商低的

2.让看的近的数看的远的

3.让靠右的数靠左的

然后我们会发现更好的选择是选择2,为什么呢?

因为你发现如果我们使用方法1或者方法3进行计数的话，我们都有一个相当难受的问题就是我们需要让两个机器人可以互相看见，而这两个机器人的视野是不同的……，此时你就会发现你可能需要相当复杂的树套树技巧才可以解决这题

然而我们让看的近的数看的远的会发生什么情况呢？

你会发现一个相当有趣的事实就是只要这个机器人能看到的就一定可以看到它

两个机器人互相可以看见的问题转化成了一个机器人可以看到另一个的问题

此时我们就相当好做这题咯

我们先把所有机器人按照视野范围倒序排序

然后我们相当于对于每一个机器人统计一下它可以和在他之前的几个机器人交流，由于排序已经帮我们解决了一维限制了，因此我们就是要统计有多个机器人的x坐标在当前机器人的[x-r,x+r]之间且这个机器人的q值在当前机器人的[q-k,q+k]之间

那么这个东西就是一个普通的矩形查询问题，我们将(x,q)视为二维平面上的一个点的话，我们发现我们需要兹次的操作就是单点加二维矩形查询

如果你够无脑的话可以写树套树，不过你发现这题的第二维相当的小(只有40)

因此我们可以直接每个q值开一个动态开点线段树，然后每次暴力的扫一遍求个和就可以解决这道题了

上代码~

#include<cstdio>
#include<algorithm>
#include<map>
using namespace std;const int N=1e5+10;typedef long long ll;
int n;int k;map <int,int> mp;int S;ll res;
struct linetree//简易动态开点线段树 
{
    map <int,int> rot;int s[22*N][2];int v[22*N];int ct;
    inline void ins(int p,int l,int r,int pos)
    {
        v[p]++;if(r-l==1){return;}int mid=(l+r)/2;
        if(pos<=mid)ins(s[p][0]=s[p][0]?s[p][0]:++ct,l,mid,pos);
        else ins(s[p][1]=s[p][1]?s[p][1]:++ct,mid,r,pos);
    }
    inline int qry(int p,int l,int r,int dl,int dr)
    {
        if((dl==l&&dr==r)||p==0){return v[p];}int mid=(l+r)/2;int res=0;
        if(dl<mid)res+=qry(s[p][0],l,mid,dl,min(dr,mid));
        if(mid<dr)res+=qry(s[p][1],mid,r,max(dl,mid),dr);return res;
    }
    inline void cins(int q,int x)
    {if(rot.count(q)==0)rot[q]=++ct;ins(rot[q],0,S,x);}
    inline int cqr(int q,int dl,int dr)
    {if(rot.count(q)==0)return 0;return qry(rot[q],0,S,dl,dr);}
}lt;
struct data//排序 
{int x;int r;int q;friend bool operator <(data a,data b){return a.r>b.r;}}a[N];
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);sort(a+1,a+n+1);
    for(int i=1;i<=n;i++){mp[a[i].x]=1;mp[a[i].x+a[i].r]=1;mp[a[i].x-a[i].r]=1;}
    map <int,int> :: iterator it,it1;
    for(it=mp.begin(),it1=it,++it1;it1!=mp.end();++it,++it1)it1->second+=it->second;
    S=mp.size();
    //for(it=mp.begin();it!=mp.end();++it)printf("(%d,%d) ",it->first,it->second);printf("\n");
    for(int i=1;i<=n;i++)//暴力统计一下就没了 
    {
        for(int j=a[i].q-k;j<=a[i].q+k;j++)res+=lt.cqr(j,mp[a[i].x-a[i].r]-1,mp[a[i].x+a[i].r]);
        lt.cins(a[i].q,mp[a[i].x]);
    }printf("%I64d",res);return 0;//拜拜程序~ 
}