2020-11-24 10:35 已编辑山东大学算法工程师

关注

牛客练习赛73 D 离别

离别

https://ac.nowcoder.com/acm/contest/9033/D

感谢 $disangan233$ 大佬提供的 $O(N)$ 思路
我稍微写的详细一点qwq
发现可以把询问离线下来，每次询问 $=k$ 的答案就是 $>=k$ 的答案减去 $>=k+1$ 的答案。
问题转变为了如何求 $>=x$ 的答案：
在询问 $[l,r]$ ，一种最直接的想法就是直接枚举 $nl,nr$ 使得 $l<=nl<=nr<=r$ 。
但是我们已经转化为 $>=x$ 的答案，所以我们可以对每个位置 $i$ 预处理出一个最小 $p_i$ 使得 $[i,p_i]$ 中出现次数最多的数出现了 $>=x$ 次，然后我们可以直接枚举 $nl$ ， $nr$ 就可以取 $[p_{nl},r]$ 的位置，即可以有 $r-p_{nl}+1$ 种取法
总的取法就是 $\sum_{nl=l}^{r}[p_{nl}<=r](r-p_{nl}+1)$
预处理 $p_i$ 开 $vector$ 看当前颜色后面第 $x-1$ 个颜色的位置，然后从后往前取 $\min$ 就行了。
所以 $p_i$ 是有单调性的，我们可以设 $j$ 为 $p_j<=r$ 的最大的数，然后枚举 $r$ 的时候移动 $j$ 。
当 $j<l$ 时，答案为 $0$
当 $j>=l$ 时
答案就变成了 $\sum_{nl=l}^{j}(r-p_{nl}+1)$
运用结合律，答案就变成了 $\sum_{nl=l}^{j}r-\sum_{nl=l}^{j}p_{nl}+\sum_{nl=l}^{j}1$
就是 $r*(j-l+1)-\sum_{nl=l}^{j}p_{nl}+(j-l+1)$
我们可以预处理前缀和 $sum_{y}=\sum_{i=1}^{y}p_{i}$ ，就可以 $O(1)$ 计算每个询问了
总的复杂度就是 $O(N+Q)$ 了
~~当然您也可以三指针一遍搞出来~~
我的代码

全部评论

推荐最新楼层

03-04 20:40

米哈游_游戏测试开发工程师(准入职员工)

米哈游内推米哈游面经

米哈游前端二面面经楼主秋招已经结束了，之前泡池子期间不敢发出来，所以打算等秋招结束后发出来，能在未来给大家参考。因为时间有些久远，楼主只能将当时的一些记录发出来，有些细节的地方可能不清楚，仅供大家参考。时间：2024-07-29持续时间：1h流程面试官说明今天面试问的三个环节： 自我介绍 + 针对项目问一些知识写一道题反问自我介绍上一段实习在联想主要做的是什么产品，采用了什么技术架构。介绍下你在联想期间使用的微前端技术。iFrame之间如何通信。介绍下你说的postMessage方法怎么做通信。假如我有一个场景，postMessage发送一个长消息时中断了，即传输中断了，你如何去做一些补偿措施...

点赞评论收藏

分享

03-03 17:26

已编辑

西安交通大学 Java

字节-中台一面凉经(以后已经与字节无缘）

1.自我介绍2.介绍JWT3.JWT和session的区别4.缓存失效的问题如何解决5.一致性问题、延迟双删6.手撕简单（最大整数和负数最大计数）手撕炸了（呜呜呜）、二分一直有个错找不出来，我是笨蛋后面面试官提示说还能优化，我死活想不起来，后面一直提示做了半小时。后面就没问结束面试了

查看7道真题和解析牛马找实习的记录软件开发笔面经

点赞评论收藏

分享

02-19 16:48

四川大学 Java

面试候选人把我删了

不用这么现实吧对你没用了就秒删隔一阵子也好呀果然当HR需要有颗大心脏😭八股不知道咋记，不知道重点，可以看看我的神品八股专栏，全网40w粉大博主也在看，介绍如下https://www.nowcoder.com/discuss/718273556131377152?sourceSSR=users

野猪不是猪🐗：发奶龙的下场

点赞评论收藏

分享

03-01 12:44

饿了么_算法工程师-AIGC(准入职员工)

饿了么内推饿了么面经

饿了么客户端开发面经饿了么一面刚面试完饿了么，分享一下热乎的面经积攒人品。面试问题：自我介绍触摸事件了解的加密机制什么是非对称加密，什么是对称加密handlerAndroid布局activity生命周期多线程通信tcp三次握手四次挥手单项链表结构协程调度算法：字符串求回文字串数目反问（提问了客户端的成长，面试官给我讲解了客户端在饿了么的成长路径，包括接触业务的核心程度、未来的技术成长路线等，可能也看出了我对客户端的疑虑，还给我分享了其实好的客户端岗位需求量从来没有减少，且因为研究的方向更专，所以相比后端，更可能成为技术专家。整体面试体验很好，面试官很专业也很耐心，我思考问题说得慢的时候会等我，...

点赞评论收藏

分享

评论

2

1

全站热榜

更多

创作者周榜

更多

正在热议

更多

# 腾讯求职进展汇总 #

370013次浏览 3012人参与

# 面试常问题系列 #

7965次浏览 254人参与

# 神州信息求职汇总 #

40602次浏览 286人参与

# 职场中你干过哪些“蠢”事 #

89627次浏览 472人参与

# 2025退税开始啦 #

13285次浏览 229人参与

# 面试时被问的最奇葩的问题 #

14947次浏览 88人参与

# 面试被问期望薪资时该如何回答 #

205570次浏览 1246人参与

# 我在牛爱网找对象 #

155107次浏览 1187人参与

# 传音控股求职进展汇总 #

5687次浏览 35人参与

# 双非本科的出路是什么？ #

105657次浏览 1030人参与

# 非技术岗投递进展 #

116875次浏览 975人参与

# 通信/硬件求职避坑tips #

39806次浏览 328人参与

# 职场新人生存指南 #

236008次浏览 5979人参与

# 如何排解工作中的焦虑 #

121566次浏览 1515人参与

# 那些我实习了才知道的事 #

164530次浏览 1391人参与

# 运营每日一题 #

54664次浏览 504人参与

# 如果有时光机，你最想去到哪个年纪？ #

37616次浏览 705人参与

# 汇川技术求职进展汇总 #

106348次浏览 736人参与

# 招银网络求职进展汇总 #

93752次浏览 601人参与

# 安克创新求职进展汇总 #

18328次浏览 144人参与

# 你觉得机械有必要实习吗 #

36356次浏览 345人参与

牛客网
牛客企业服务