CodeForces 1045G AI robots（CDQ分治 + 树状数组 + 单调队列）_codeforces cdq-程序员宅基地

技术标签：树状数组 CodeForces ------------数据结构----------- 单调队列 ---------Online Judge-------- --------------分治-------------- CDQ分治

大致题意：有很多个机器人，他们要相互交流有一些限制条件。首先是，两个人要相互能够能够看到；其次，两个人的智商的差不超过K。现在给出每个机器人的视力范围和他们的智商，现在问你总共有多少对机器人能够相互交流。

首先来看下总共有多少个限制条件。由于是要求双方都能够看到，所以显然是要按照视野半径去排序的。然后要求两个人的智商差要在一定的范围内的，所以也要按照智商去排序。另外还要跟自己的位置有关。根据这个，我们可以构造出分治的大致方法：首先按照半径去排序，半径大的在前面，因为这样如果后面的东西能够看到前面，那么前面的东西一定能看到后面，符合cdq分治前面更新后面的要求；然后分治的过程中归并排序按照智商的大小去排序，因为这样可以利用一些单调性，同时好确定智商差；最后就是用一个离散化的树状数组去维护每个位置的机器人数量。

前面和最后的都好说，关键是如何利用智商差去求能够相互看到的机器人的对数。这里我们用到了单调队列。由于是按照智商的大小来进行分治的。所以前一半和后一半已经是按照智商的大小排好序了的，所以说我们可以利用单调性。根据cdq分治的原则，前面一半去更新后面一半，所以我们考虑对于后一半的每个机器人，单独计算贡献。对于后一半的第i个机器人，我可以在前一半确定一个区间[j,k]，在这个区间内的所有机器人与机器人i的智商差不超过K。把这个区间内的所有机器人添加到树状数组中，然后贡献就是机器人i视野范围内的机器人数目。然后再往后考虑后一半的其他机器人。由于前一半和后一半的智商是递减的，所以从i移动到i+1区间的移动只会单调往后移动，符合单调队列性质。这样前一半的每一个机器人只会进出队列各一次，对应加入和移出树状数组各一次。所以这个部分均摊的时间复杂度是O(NlogN)的，这个log来自树状数组。

如此我们就求出了合并的时候前面对后面产生的贡献。总的时间复杂度就是O(NlogNlogN)。具体见代码：

#include<bits/stdc++.h>
#define LL long long
#define N 100010

using namespace std;

struct node{int x,r,iq,L,R;} p[N],tmp[N];
int n,tot,K,x[N<<2],q[N]; LL ans=0;

struct BinaryIndexedTree
{
    int c[N<<2];

    inline void update(int x,int k)
    {
        x=min(x,tot);
        for(;x<=tot;x+=x&-x) c[x]+=k;
    }

    inline int getsum(int x)
    {
        int ans=0;
        for(;x>0;x-=x&-x) ans+=c[x];
        return ans;
    }

} BIT;

bool cmp1(node a,node b)
{
    return a.r>b.r;
}

bool cmp2(node a,node b)
{
    return a.iq>b.iq;
}

void cdq(int l,int r)
{
    if (l==r) return;
    int mid=(l+r)>>1;
    cdq(l,mid);
    cdq(mid+1,r);
    int h=0,t=0;
    for(int i=mid+1,j=l;i<=r;i++)
    {
        while(j<=mid&&p[j].iq-p[i].iq>K) j++;
        while(j<=mid&&abs(p[j].iq-p[i].iq)<=K)
        {
            BIT.update(p[j].x,1);
            q[t++]=j++;
        }
        while(h<t&&abs(p[q[h]].iq-p[i].iq)>K)
        {
            BIT.update(p[q[h]].x,-1);
            h++;
        }
        ans+=BIT.getsum(p[i].R)-BIT.getsum(p[i].L-1);
    }
    for(;h<t;h++) BIT.update(p[q[h]].x,-1);
    inplace_merge(p+l,p+mid+1,p+r+1,cmp2);
}

int main()
{
    scanf("%d%d",&n,&K);
    for(int i=1;i<=n;i++)
    {
        int X,Y,Z;
        scanf("%d%d%d",&X,&Y,&Z);
        p[i]=node{X,Y,Z,0,0};
        x[++tot]=X; x[++tot]=X-Y; x[++tot]=X+Y;
    }
    sort(x+1,x+tot+1);
    tot=unique(x+1,x+tot+1)-x-1;
    for(int i=1;i<=n;i++)
    {
        p[i].L=lower_bound(x+1,x+tot+1,p[i].x-p[i].r)-x;
        p[i].R=lower_bound(x+1,x+tot+1,p[i].x+p[i].r)-x;
        p[i].x=lower_bound(x+1,x+tot+1,p[i].x)-x;
    }
    sort(p+1,p+n+1,cmp1);
    cdq(1,n);
    printf("%lld\n",ans);
    return 0;
}

本文链接：https://blog.csdn.net/u013534123/article/details/83241568

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

HTML5中的video插件_html5 前端 video 兼容格式转换插件-程序员宅基地

文章浏览阅读3.5k次，点赞2次，收藏2次。在HTML5中，新增了两个元素---video元素与audio元素。video元素专门用来播放网络上的视频或电影，而audio元素专门用来播放网络上的音频数据。使用这两个元素，就不在需要使用其他插件了，只需要支持HTML5的浏览器即可。今天，我们在这里就详细的说说video元素它（video）的作用是用于播放视频。它所主要支持的文件格式有webm、ogg、MP4、MP3、WAVE。它的用法..._html5 前端 video 兼容格式转换插件

38、使用Clion2020导入静态包Gflag和Glog_clion自动导入包-程序员宅基地

文章浏览阅读625次。基本思想:简单学习了一下移植Google的日志包，以备后续跨平台直接使用；首先编译生成静态包，如果需要夸平台需要修改对应的编译器ubuntu@ubuntu:git clone https://github.com/gflags/gflags.gitubuntu@ubuntu:cd gflags/ubuntu@ubuntu:~/gflags$ mkdir buildubuntu@ubuntu:~/gflags/build$ cmake ..ubuntu@ubuntu:~/gflags/bui_clion自动导入包

“码农”一词是怎么来的？为什么中国程序员会被码农？程序员和农民有什么关联？-程序员宅基地

文章浏览阅读1.7w次。原创：思齐大神来源：蚁开源社区很多同学会问，IT行业在中国并不是特别差的行业，而程序员的工资也并不低，但为什么中国的程序员总被称作码农或者说是苦逼的程序员？中国的程序员生活和欧美的有什么不一样？先说两个小段子街边，一对情侣在吵架。女孩对男孩说，“我们分手吧！”男孩沉默半天，开口问道，“我能再说最后一句话吗？”“说吧，婆婆妈妈的。”“我会编程……”“会编程有个屁用啊，现在到处都是会编程的人！”男孩涨红了脸，接着说道，“我会编程……我会变成…童话里，你爱的那个天使……”【程序._码农

Java初学者也能看的懂的AQS_aqs对接-程序员宅基地

文章浏览阅读259次。Java初学者也能看的懂的AQS学习AQS之前，你需要了解以下内容，如果不是很清楚，那么理解本文会有点吃力。（Java初学者得会一下内容）synchronizedCASLock前言synchronized首先我们知道synchronized是Java关键字，上锁释放锁等一切操作都是由JVM控制的。我们只能通过虚拟机的C++才能去研究其底层实现。我们除了判断synchronized是作为方法的修饰符，还是当做同步代码块使用以外，没什么需要我们程序员操作的。cas一种自旋的原子操作，也是J_aqs对接

【JZOJ5262】【GDOI2018模拟8.12】树(DP，性质题)_gdoi2018省选模拟树-程序员宅基地

文章浏览阅读460次。DescriptionSolution首先我们可以知道两个性质：1、路径u-v和路径v-w可以合并为路径u-w；2、路径u1-v1加路径u2-v2和路径u1-v2加路径u2-v1是等价的(就是起始点和终点可以互换) 那么知道这些性质之后就很好做了。我们只用知道每个点多少次做起点和多少次做终点。我们设f[i]表示满足i子树的需求i上的值要是多少。那么枚举i的所有儿子，判断a[i]-f[i]，_gdoi2018省选模拟树

[PTA]7-65 字符串替换 (15 分)含思路_字符串替换pta-程序员宅基地

文章浏览阅读2.8k次，点赞4次，收藏28次。我们进行简单的运算即可实现倒序。_字符串替换pta

随便推点

myeclipse工作目录上的.metadata文件夹可以删除_metadata可以删除吗-程序员宅基地

文章浏览阅读3.3k次。不能删除。看看文件夹下的内容就知道：1、me_tcat：是MyEclipse记录的当前工作空间中的配置，比如当前工作空间中有哪些工程，打开了哪些文件java类，编辑了哪些文件和Java类，MyEclipse会在启动时加载这个文件夹下的内容。如果删除了，再次打开MyEclipse会发现工作空间是空的，需要重新导入工程。2、plugins：当前工作空间用到了哪些IDE插件，和程程序无关_metadata可以删除吗

SeetaFace2 Android 平台编译_seetafacerecognizer2.0.ats-程序员宅基地

文章浏览阅读4.1k次。SeetaFace2 Android 平台编译项目地址：https://github.com/seetafaceengine/SeetaFace2SeetaFace2 人脸识别引擎包括了搭建一套全自动人脸识别系统所需的三个核心模块，即：人脸检测模块 FaceDetector、面部关键点定位模块 FaceLandmarker 以及人脸特征提取与比对模块 FaceRecognizer。面部关键点定位支持 5 点和 81 点定位，两个辅助模块 FaceTracker 和 QualityAssessor 用_seetafacerecognizer2.0.ats

Oracle删除约束和主键的语句_oracle删除主键的sql语句-程序员宅基地

文章浏览阅读3.2w次，点赞4次，收藏34次。1.删除约束语句：alter table 表名 drop constraint 约束名；alter table mz_sf4 drop constraint pk_id1;2.删除主键语句：alter table 表名 drop primary key;alter table mz_sf3 drop primary key;如果出错：ORA-02273：此唯一主键已_oracle删除主键的sql语句

MySQL~InnoDB的备份和主从复制-程序员宅基地

文章浏览阅读989次，点赞9次，收藏13次。这份面试题几乎包含了他在一年内遇到的所有面试题以及答案，甚至包括面试中的细节对话以及语录，可谓是细节到极致，甚至简历优化和怎么投简历更容易得到面试机会也包括在内！也包括教你怎么去获得一些大厂，比如阿里，腾讯的内推名额！某位名人说过成功是靠99%的汗水和1%的机遇得到的，而你想获得那1%的机遇你首先就得付出99%的汗水！你只有朝着你的目标一步一步坚持不懈的走下去你才能有机会获得成功！成功只会留给那些有准备的人！《一线大厂Java面试题解析+核心总结学习笔记+最新讲解视频+实战项目源码》点击传送门即可获取。

大数据平台核心技术学堂在线雨课堂第八讲作业答案人文交流月_vertectorization-程序员宅基地

文章浏览阅读2k次。关于Vertectorization哪些是正确的（）相对于其他编程模型，sql在大数据领域有哪些好处（）哪些部分适合做codegen（）关于内存计算描述不正确的有（）_vertectorization

java汉字拼音简码_java生成首字母拼音简码的总结-程序员宅基地

文章浏览阅读306次。百度找到了某论坛高人写的java(具体论坛记不清了)，直接用来调用，再次非常感谢，基本上实现了我的需求package MD5;import java.util.Scanner;public class ChineseToPinYin {/*** 汉字转拼音缩写** @param str* 要转换的汉字字符串* @return String 拼音缩写*/public Strin..._java生成拼音码