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

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

智能推荐

C++ Json到对象的自动序列化和反序列化工作_c++ json序列化和反序列化-程序员宅基地

文章浏览阅读555次，点赞17次，收藏22次。JSERIALIZE_DEF_OBJECTLIST(Person,Object,objectList) //接受json中的objectList对象数组，对象数组使用此宏定义。JSERIALIZE_DEF_OBJECTTYPE(Person,Son,son) //接受json中的son对象，对象成员使用此宏定义。//输出反序列化结果。

DOSBOX 0.74模拟器安装Windows 95_dosbox imgmount-程序员宅基地

文章浏览阅读7.8k次，点赞2次，收藏6次。DosBox本身带有5.0版的DOS系统，启动后虚拟一个Z盘存放有Dosbox特有的外部指令，如config.com、imgmount.com等，经测试，可以顺利安装各版本的windows 3.1系统，但是不能安装win95，需要用原版的dos镜像启动才能安装。1. 获取启动盘镜像文件下载Win95启动软盘镜像文件，名为boot.img，放到DosBox 0.74的目录下。2. 制作硬盘镜像文件_dosbox imgmount

呼叫转移的普适性及编程实现_电话自动转移程序开发-程序员宅基地

文章浏览阅读53次。总结来说，呼叫转移是一种方便的电话通信功能，在编程中可以通过使用电话服务提供商的API来实现。然而，实际的实现可能因具体的服务提供商而有所不同，你需要参考相应的文档或与服务提供商联系以获取准确的实现细节。在函数内部，我们构建了一个API请求的有效载荷（payload），其中包含了原始电话号码和目标电话号码。在编程中，呼叫转移的实现涉及使用电话通信协议和相应的编程语言。需要注意的是，实际的呼叫转移功能的实现可能因电话服务提供商的不同而有所差异。首先，我们需要确保已经安装了Python的开发环境和相应的库。_电话自动转移程序开发

FLink聚合性能优化--MiniBatch分析_flink mini-batch-程序员宅基地

文章浏览阅读5.4k次，点赞4次，收藏15次。[@ TOC]一、MiniBatch的演进思路1、MiniBatch版本Flink 1.9.0 SQL(Blink Planner) 性能优化中一项重要的改进就是升级了微批模型，即 MiniBatch(也称作MicroBatch或MiniBatch2.0)，在支持高吞吐场景发挥了重要作用。MiniBatch与早期的MiniBatch1.0在微批的触发机制略有不同。原理同样是缓存一定的数据后..._flink mini-batch

EasyExcel导入_easyexcel 对接multipartfile-程序员宅基地

文章浏览阅读808次，点赞6次，收藏6次。导入依赖<dependency> <groupId>com.alibaba</groupId> <artifactId>easyexcel</artifactId> <version>2.1.6</version></dependency>Controllerimport java.text.ParseException;import org.springframework._easyexcel 对接multipartfile

英飞凌TC3xx之一起认识DSADC系列（一）架构介绍-程序员宅基地

文章浏览阅读2.7k次，点赞27次，收藏42次。一文清晰了解英飞凌TC3xx系列的架构和组成部分，适用于正在使用EDSADC功能的人们。_dsadc

随便推点

2022考研日语71分自学经验贴；日语可以自学吗？-程序员宅基地

文章浏览阅读1.2k次，点赞3次，收藏5次。目录1 个人对考研日语的评价1 日语VS英语2 考研日语适合哪些人，什么时候开始3 找到可以选日语的院校专业的方法4 高考日语自学经历（供参考）4.1 学习过程4.2 必用资料5 考研日语自学+作文课经历（供参考）5.1 资料相关5.2 完型（20分）5.3 阅读（40分）5.4 翻译（15分）5.5 作文（25分）end实在受不了英语应试的折磨，高考和考研都用了203日语替换了英语（高考127分，考研估分65-70分）1 个人对考研日语的评价我是有了高考127分的基础（大概N3水平，N2擦线水平），

JVM性能优化 (一) 初识JVM-程序员宅基地

文章浏览阅读703次，点赞22次，收藏24次。到这里文章就讲完了，有疑问的兄弟可以在下面讨论或留言，也祝大家在今年开开心心，健健康康，能够拥有一份好工作，大家加油，我是牧小农！自我介绍一下，小编13年上海交大毕业，曾经在小公司待过，也去过华为、OPPO等大厂，18年进入阿里一直到现在。深知大多数Java工程师，想要提升技能，往往是自己摸索成长或者是报班学习，但对于培训机构动则几千的学费，着实压力不小。自己不成体系的自学效果低效又漫长，而且极易碰到天花板技术停滞不前！

通过手动给upx去壳简单了解逆向_upx脱壳机-程序员宅基地

文章浏览阅读1.7k次。对于像我这种想入门逆向的，这种方式真的可以培养兴趣，也从中学到了很多知识，我也不会仅仅止步于脱upx的。[外链图片转存中…(img-xkCBlSoD-1693021558445)]即可。对于像我这种想入门逆向的，这种方式真的可以培养兴趣，也从中学到了很多知识，我也不会仅仅止步于脱upx的。_upx脱壳机

Quartz定时任务调度cron 表达式时间格式(☆)_cron表达式下午5点30-程序员宅基地

文章浏览阅读890次。cron 表达式的格式 Quartz Cron 表达式支持到七个域名称是否必须允许值特殊字符秒是 0-59 ..._cron表达式下午5点30

SQL Server 疑难杂症--转换科学计数法的数值字符串为decimal类型_mssql 字符串转decimal 精度问题-程序员宅基地

文章浏览阅读1.8k次。今天在操作数据库时，需要将字符串转换成Decimal类型。代码如下：selectcast('0.12'asdecimal(18,2));selectconvert(decimal(18,2),'0.12');当需要将科学计数法的数字字符串转换成Decimal时，这2种写法都报错：Msg 8114, Level 16, State 5, Line 1Erro..._mssql 字符串转decimal 精度问题

soul源码解读（十八）-- resilience4j插件原理分析_resilience4j timeoutduration含义-程序员宅基地

文章浏览阅读553次。soul源码解读（十八）resilience4j插件使用resilience4jresilience4j插件是网关用来对流量进行限流与熔断的可选选择之一。resilience4j为网关熔断限流提供能力。插件使用1.启动 admin，打开 resilience4j 插件开关2.在 bootstrap 项目的 pom 文件引入 resilience4j 插件的相关依赖，启动 bootstrap  <_resilience4j timeoutduration含义