P11118 [ROI 2024 Day 2] 无人机比赛 题解

Description

n n n 架无人机参与比赛,第 i i i 架无人机飞过一个单位距离需 t i t_i ti 秒。

赛道为一条直线,上面有 m m m 个存档点,第 i i i 个存档点距起点 s i s_i si 个单位长度,保证 s i + 1 > s i s_{i+1}>s_i si+1>si

一共有 n n n 场比赛,第 k k k 场比赛有前 k k k 架无人机参加,比赛按如下方式进行。

定义一个阶段为当前还未完赛的所有无人机从其存档点开始飞行,直到有一架无人机到达了下一个存档点,我们称这架无人机为此阶段的赢家。若有多架无人机同时到达,则编号最小的为赢家。

该阶段结束后,所有非赢家的无人机将被传送回此阶段开始时其所在的存档点,而赢家则更新其存档点。若赢家此时到达了第 m m m 个存档点,那么它将完赛,后面的阶段都不参加。

当所有无人机都完赛时,那么这场比赛就结束了。

你需要对于这 n n n 场比赛中的每一场,分别求出比赛中所有无人机的传送次数之和。

Solution

依题意得一个阶段中只有赢家改变存档点,对非赢家造成传送,而非赢家之间的相对位置都不改变,不会互相造成传送。

于是总传送次数可以拆成两两之间所造成的贡献之和,并且这只与它们两有多少个阶段输赢不同有关,即对于 i , j i,j i,j,两机互相造成的贡献为 i , j i,j i,j 中第一架无人机完赛时,已经经过了多少个阶段。

对于一架无人机 i i i,我们定义 w j = ( s j − s j − 1 ) × t i w_j=(s_j-s_{j-1})\times t_i wj=(sjsj1)×ti

那么对于 i , j i,j i,j 算贡献,可以通过归并 i , j i,j i,j 的两个 w w w 序列来求出。然而 w w w 并不有序,但我们可以通过 UR #26 石子合并 中的结论,即对于同一序列的 w w w,若 w i + 1 ≤ w i w_{i+1}\le w_i wi+1wi 那么 w i + 1 w_{i+1} wi+1 会在 w i w_i wi 弹出后紧接地弹出,在归并后的数组中相邻。

而同一组中的 w w w 大小关系与 t t t 无关,与 s s s 的差分数组有关,所以可以对 s s s 的差分数组进行操作,将会紧邻弹出的数合在一起,设其总共有 k k k 个这样的段。每个段计 a i , b i a_i,b_i ai,bi,表示这一段段头的值以及这一段的长度。

因为 a i a_i ai 是严格递增的,那么由于 a 1 + a 2 + ⋯ + a k = s m ≤ 1.5 × 1 0 5 a_1+a_2+\cdots+a_k=s_m\le1.5\times10^5 a1+a2++ak=sm1.5×105,所以 k k k 的大小是 O ( V ) O(\sqrt{V}) O(V ) 的, V V V 1.5 × 1 0 5 1.5\times10^5 1.5×105 级别的。

回到对 i , j ( i < j ) i,j(i<j) i,j(i<j) 算贡献,发现比较好算了:

  • t i ≤ t j t_i\le t_j titj,那么 i i i 先完赛,先加上 m m m 的贡献,即 i i i j j j 造成的贡献。 j j j i i i 造成的贡献就是看在 i i i 完赛时, j j j 到了第几个存档点,也就是找到最大的 x x x 使得 a k × t i > a x × t j a_k\times t_i>a_x\times t_j ak×ti>ax×tj,然后加上 b 1 + b 2 + ⋯ + b x b_1+b_2+\cdots+b_x b1+b2++bx 的贡献。

  • t i > t j t_i>t_j ti>tj,那么 j j j 先完赛,同样先加上 m m m 的贡献。然后找到最大的 x x x 使得 a x × t i ≤ a k × t j a_x\times t_i\le a_k\times t_j ax×tiak×tj,同样加上 b 1 + ⋯ b x b_1+\cdots b_x b1+bx 的贡献,注意是 小于等于,因为 i < j i<j i<j,所以当两人用时相等时赢家是 i i i

x x x 用二分,那么至此我们用 O ( n 2 log ⁡ V ) O(n^2\log\sqrt{V}) O(n2logV ) 的复杂度解决了问题,比暴力分多 10 10 10 分,可喜可贺。

那么怎么继续优化呢?

考虑上扫描线,我们从小到大扫 i i i,对于每一个可能的 x x x,先二分找到 j j j 的限制(两种情况),再对这两段区间加上 b x b_x bx,注意我们已经把贡献分成了 m m m b 1 + ⋯ + b x b_1+\cdots+b_x b1++bx

计算答案就是扫到 j j j 时,取出其在线段树内的值,然后加上 j × ( j − 1 ) 2 × m \dfrac{j\times(j-1)}{2}\times m 2j×(j1)×m 的贡献。

注意线段树上维护的是 离散后的 t t t 的值,二分也是找离散后的值,同时要 先算贡献再查值,不然若 t i = t j t_i=t_j ti=tj 时会重复算贡献。

现在时间复杂度变为了 O ( n V ( log ⁡ n + log ⁡ n ) ) O(n\sqrt{V}(\log n+\log n)) O(nV (logn+logn)),前面的 log ⁡ \log log 是二分,后面的 log ⁡ \log log 是区间修改,单点查询的线段树。但这个复杂度跑不过去,需要进一步优化。

注意到区间修改有 O ( n V ) O(n\sqrt{V}) O(nV ) 级别,而询问只有 O ( n ) O(n) O(n) 级别,那么可以用区间修改 O ( 1 ) O(1) O(1),单点查询 O ( n ) O(\sqrt{n}) O(n ) 的分块来平衡复杂度,具体的,维护每个点和每个块的差分数组,修改时修改两个点和两个块的值,查询即查询差分数组的前缀和。

但二分的 O ( log ⁡ n ) O(\log n) O(logn) 还没去掉,观察到当 x x x 相同时, i i i 递增时,其对应 j j j 的限制也递增, i , j i,j i,j 是离散后 t t t 数组的下标。那么可以预处理出 t a g i , x tag_{i,x} tagi,x,表示二分出来的限制,用双指针维护做到时间 O ( n V ) O(n\sqrt{V}) O(nV ),空间 O ( n V ) O(n\sqrt{V}) O(nV )。注意两种限制的双指针有所不同,细节较多。

这个题就用时间 O ( n ( V + n ) ) O(n(\sqrt{V}+\sqrt{n})) O(n(V +n )),空间 O ( n V ) O(n\sqrt{V}) O(nV ) 的复杂度做完了,吗?

实际上 k k k 的极限并不是 1.5 × 1 0 5 \sqrt{1.5\times10^5} 1.5×105 ,而是 550 550 550 。所以开两个 t a g tag tag 会爆空间,不过只要先处理一种,算贡献,再处理另外一种,算贡献就可以了。

时间上有略微卡常,只需在求 t a g tag tag 时使访问较为连续即可,先枚 i i i,再枚 x x x

还有一些细节具体见代码。

Code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n,m,k,cnt,len;
int t[150010],s[150010],tt[150010],id[150010];
int tag[150010][560];
int st[150010],hd;
int a[560],b[560];
ll fin1[150010],fin2[560],ans[150010];
void init(){cin>>n>>m;for(int i=1;i<=n;i++){cin>>t[i],tt[i]=t[i];}sort(tt+1,tt+1+n);cnt=unique(tt+1,tt+1+n)-tt-1;len=sqrt(cnt)+1;for(int i=1;i<=n;i++){t[i]=lower_bound(tt+1,tt+1+cnt,t[i])-tt;}for(int i=1;i<=cnt+1;i++){id[i]=(i-1)/len+1;}for(int i=1;i<=m;i++){cin>>s[i];}for(int i=m;i;i--){while(hd&&s[st[hd]]-s[st[hd]-1]<=s[i]-s[i-1]) hd--;st[++hd]=i;}st[0]=m+1;for(int i=hd;i;i--){a[++k]=s[st[i]]-s[st[i]-1];b[k]=st[i-1]-st[i];}
}
void update(int l,int r,ll v){  //O(1)更新fin1[l]+=v,fin1[r+1]-=v;fin2[id[l]]+=v,fin2[id[r+1]]-=v;
}
ll query(int x){  //O(sqrt(n)) 查询ll sum=0;for(int i=1;i<id[x];i++){sum+=fin2[i];}for(int i=(id[x]-1)*len+1;i<=x;i++){sum+=fin1[i];}return sum;
}
void pres1(){  //ti<=tjfor(int j=1;j<=cnt;j++){for(int i=1;i<=k;i++){int fl=tag[j-1][i];while(1){tag[j][i]=fl;if(fl+1>cnt||(ll)tt[j]*a[k]<=(ll)tt[fl+1]*a[i]) break;fl++;}}}
}
void pres2(){  //ti>tj,两个双指针细节多,一定要理解充分for(int j=1;j<=cnt;j++){for(int i=1;i<=k;i++){int fl=tag[j-1][i];while(1){if((ll)tt[j]*a[i]<=(ll)a[k]*tt[fl]){tag[j][i]=fl;break;}fl++;}}}
}
void solve(){pres1();for(int i=1;i<=n;i++){ans[i]=query(t[i]);for(int j=1;j<=k;j++){if(tag[t[i]][j]>=t[i]){update(t[i],tag[t[i]][j],b[j]);}}}pres2();for(int i=1;i<=cnt;i++) fin1[i]=0;  //记得清空分块for(int i=1;i<=id[cnt+1];i++) fin2[i]=0;for(int i=1;i<=n;i++){ans[i]+=ans[i-1]+query(t[i]);cout<<ans[i]+(ll)i*(i-1)/2*m<<'\n';for(int j=1;j<=k;j++){if(tag[t[i]][j]<t[i]){update(tag[t[i]][j],t[i]-1,b[j]);}}}
}
int main(){ios::sync_with_stdio(0);cin.tie(nullptr);init();solve();return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/7941.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

固定宽度--文字多少不一样--需要文字充满整个宽度

固定宽度–文字多少不一样–需要文字充满整个宽度 1.场景–登陆页面 这样显示显然不太行 那我们想要是这种情况吗–用户名和密码都充满真个宽度的div 2.代码实现—其中一个重要属性最为关键 text-align-last: justify css <style>.user{width:60px;background-colo…

艾体宝产品丨加速开发!Redis Copilot智能助手上线

我们最近发布了 Redis Copilot&#xff0c;旨在帮助开发者更加高效地使用 Redis 构建应用。提升应用性能&#xff0c;简化构建过程是我们不懈的追求。Redis Copilot 正是为此而生的人工智能助手&#xff0c;助力开发者迅速掌握 Redis 的使用技巧。现在您可以在 Redis Insight 中…

4种鼓励创业创新的方法

随着市场趋于饱和&#xff0c;许多企业&#xff0c;尤其是初创企业&#xff0c;很难在竞争中保持领先地位。技术为企业彻底改变其营销和管理策略铺平了道路。另一个经过实践检验的成功渗透特定市场的方法是在办公室内部激发创新&#xff0c;从员工到品牌皆如此。 那么究竟如何…

Spark的yarn集群环境搭建

一.为什么要搭建yarn集群 为什么要将Spark的程序运行在YARN上&#xff0c;不运行在自带的 Standalone集群上&#xff1f; 1、统一化资源管理 Standalone是Spark专用的资源管理集群&#xff0c;只能用于运行 Spark程序 YARN是功能的分布式资源管理平台&#xff0c;可以运行各种分…

【react使用AES对称加密的实现】

react使用AES对称加密的实现 前言使用CryptoJS库密钥存放加密方法解密方法结语 前言 项目中要求敏感信息怕被抓包泄密必须进行加密传输处理&#xff0c;普通的md5加密虽然能解决传输问题&#xff0c;但是项目中有权限的用户是需要查看数据进行查询的&#xff0c;所以就不能直接…

登录功能设计(php+mysql)

一 登录功能 1. 创建一个登录页面&#xff08;login.php&#xff09;&#xff0c;包含一个表单&#xff0c;用户输入用户名和密码。 2. 在表单的提交事件中&#xff0c;使用PHP代码处理用户输入的用户名和密码。 3. 首先&#xff0c;连接MySQL数据库。然后&a…

ReactPress 是什么?

ReactPress Github项目地址&#xff1a;https://github.com/fecommunity/reactpress 欢迎Star。 ReactPress 是什么&#xff1f; ReactPress 是使用React开发的开源发布平台&#xff0c;用户可以在支持React和MySQL数据库的服务器上架设属于自己的博客、网站。也可以把 ReactP…

ai外呼机器人的作用有哪些?

ai外呼机器人具有极高的工作效率。日拨打成千上万通不是问题&#xff0c;同时&#xff0c;机器人还可以快速筛选潜在客户&#xff0c;将更多精力集中在有价值的客户身上&#xff0c;进一步提升营销效果。183-3601-7550 ai外呼机器人的作用&#xff1a; 1、搭建系统&#xff0c…

福禄克DTX,DSX系列内置标准以及生成的测试报告如何解读?

今日,接到一些朋友的询问?虽然使用了很长一段时间的FLUKE DSX-5000或者DSX-8000,但是对于测试标准和测试生成的报告一知半解,借此咱们一块屡屡清楚。 1,经常有的朋友拿到设备后,第一时间就问,咱们福禄克内置的标准的多少?我线的参数(被测的铜缆)达到多少db,才能算过…

我与Linux的爱恋:磁盘的存储管理

​ ​ &#x1f525;个人主页&#xff1a;guoguoqiang. &#x1f525;专栏&#xff1a;Linux的学习 文章目录 磁盘的存储管理 磁盘的存储管理 在我们日常生活中&#xff0c;我们要打开很多文件(要打开这个文件需要先找到这个文件->要在磁盘中先找到->通过文件路径文件…

git原理与上传

言&#xff1a; git是一个软件&#xff0c;gitee/github是一个网站&#xff0c;这里有什么联系吗&#xff1f;我们身为一个程序员不可能不知道github&#xff0c;但是毕竟这是外国的网站&#xff0c;我们不翻墙的情况下&#xff0c;是无法访问的(或者就是太慢了&#xff0c;或…

Python基础学习_01

目录 1、注释 2、数字和数学计算 3、变量 4、字符串 5、打印 6、本节总结 1、注释 • 什么是注释&#xff1f; 1&#xff09;注释就是用自然语言向代码阅读者说明代码的功能和意义 • 注释 1&#xff09;单行注释使用 # 为开头&#xff1b;并且不能换行…

操作系统学习笔记-3.2虚拟内存

文章目录 虚拟内存请求分页管理方式页面置换算法最佳置换算法工作原理OPT 算法的示例最佳置换算法的优点和缺点 先进先出置换算法最近最久未使用时钟置换算法时钟置换算法的工作原理&#xff1a;算法的步骤&#xff1a; 改进型时钟置换算法改进型时钟置换算法的特点&#xff1a…

vue3 封装aixos

1. Vue3 封装 aixos 并且 使用 aixos 请求数据 npm install axios # 或者 yarn add axios 2. Vue3 封装 aixos 并且 使用 aixos 请求数据 封装 axios可以帮助我们更好地管理 HTTP 请求&#xff0c;例如添加统一的基础URL、请求头、拦截器等功能。 下面是封装 axios的一个示…

量子计算机能解决哪些问题?

经典与量子难度对比 在深入示例之前&#xff0c;我们首先讨论一下如何研究和分类各种问题的难度。有些问题可以在经典计算机上轻松解决&#xff0c;我们不需要量子计算机来解决它们。另一方面&#xff0c;有些问题非常困难&#xff0c;需要量子计算机来解决。一个著名的例子是寻…

中电金信:院长寄语|关于源启AI+行动的思考

中国电子首席科学家 中电金信研究院院长 况文川 自2022年8月19日发布以来&#xff0c;源启已经走上了她第三年的征途。今天&#xff0c;源启已经成为公司战略的支点&#xff0c;中电金信正致力于用“源启底座”“源启咨询”“源启应用重构”三位一体的方式来赋能千行百业数智化…

海康私有化视频平台EasyCVR视频分析设备平台流媒体协议RTMP、HTTP-FLV、HLS的简单对比

在当今的数字化世界中&#xff0c;视频流协议的选择对于确保流畅、高效的视频传输至关重要。随着互联网技术的快速发展&#xff0c;直播和视频点播服务已经成为人们日常生活中不可或缺的一部分。无论是安防监控、在线教育、远程会议还是娱乐直播&#xff0c;用户对于视频流的实…

详解使用python读写csv,以及将csv数据写入数据库

csv文件 csv介绍 CSV&#xff0c;也即Comma-Separated Values&#xff0c;是一种用于存储表格数据的纯文本文件格式&#xff0c;其中每一行代表一条记录&#xff0c;记录中的各个字段由逗号分隔。 姓名,年龄,性别 张三,25,男 李四,28,男 王五,22,男 六六,29,女 子柒,28,女 对…

OpenMVS OpenMVG 笔记

OpenMVS & OpenMVG 笔记 OpenMVS 和 OpenMVG 都是计算机视觉中用于三维重建的开源库。两者都可以实现从图像集合中计算出相机位姿和三维点云&#xff0c;但它们的重点略有不同。 OpenMVG 主要关注于从输入图像集合中提取稠密的特征匹配&#xff0c;通过这些匹配计算相机的…

Golang--文件操作

1、文件 文件&#xff1a;文件用于保存数据&#xff0c;是数据源的一种 os包下的File结构体封装了对文件的操作&#xff08;记得包os包&#xff09; 2、File结构体--打开文件和关闭文件 2.1 打开文件 打开文件&#xff0c;用于读取&#xff08;函数&#xff09;&#xff1a; 传…