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)$ 了
~~当然您也可以三指针一遍搞出来~~
我的代码

全部评论

推荐最新楼层

10-14 10:20

海康威视_自动化开发工程师(准入职员工)

海康威视内推，海康威视内推码

岗位：武汉 嵌入式开发timeline：8.30 测评，10.9 一面，10.11 二面一面技术：自我介绍讲下实习经历平常怎么debug项目中有没有遇到什么问题，怎么解决的介绍一下学校经历了解数据结构吗？基本的数据结构？查找搜索效率？有什么方法可以提高效率？具体围绕数据结构问了很多RTOS，多任务操作反问：做存储固件的，具体的进来再分二面HR：北京线下，地点在北京研发中心，具体内容就是唠家常，一些HR面的基本问题销售工程师工作体验，总结累但成长很多。1.大家最先关注的就是HIK的工作压力，只能说体面厂没有辜负盛名！名不虚传！我来这边是销售岗，基本上每天都要差不多11点下班。因为销售不仅需要对接...

点赞评论收藏

分享

10-17 10:36

北京理工大学算法工程师

无论文勇闯秋招算法岗——淘天智能搜推部一面（复盘，草稿）

一共1h。项目简单介绍。10min左右。然后就是结合实习项目的 35min 的各种八股提问。最后15min做题。给了三个题，我选的 岛屿的个数，hot100里边的。其它两个好像也是hot100里边的（有个三数之和）。反问环节，是什么方向，搜索。有什么面试建议，语速可以快一点（笑），这样可以聊更多的东西。记录一下八股部分。VideoMAE怎么训练的？CLIP和MAE有什么区别？BLIP的B什么意思？BLIP2的qformer是怎么训练的？有几个loss？ITC和ITM的区别？强化学习，GRPO和PPO的区别？重要性采样是用来干嘛的？拒绝采样和重要性采样有什么不同或者一样的地方？flashatte...

查看13道真题和解析

点赞评论收藏

分享

10-14 21:00

门头沟学院 Java

不面试就可以去实习了，这靠谱吗？给我整害怕了😂

吃花椒的狸猫：这个人说的倒是实话，特别是小公司，一个实习生哪里来的那么多要求

点赞评论收藏

分享

10-13 22:56

门头沟学院 C++

签浪潮还是等小米

rt，鼠鼠的浪潮网签明天过期，鼠鼠是山东人，好像自己也能接受。之前的面试大厂基本挂干净了，剩下小米二面后在泡，问了下面试官没有挂，但要泡。还有海信似乎也通过了，不过在深圳，鼠鼠也不是很想去。其它还有一些公司应该陆陆续续还有一些面试，现在有些纠结是直接签了还是再等再面呢？大佬们能不能给鼠鼠提一些意见，万分感谢！！！

牛客78696106...：浪潮可不是开摆，当初我还是开发的时候我组长跟我说他们组有段时间天天1，2点走，早上5点就来，全组肝出来心肌炎，浪潮挣钱省立花可不是说说，当然也看部门，但是浪潮普遍就那dio样，而且你算下时薪就知道不高，没事也是9点半走，不然算你旷工

投递小米集团等公司10个岗位

点赞评论收藏

分享

评论

3

1

全站热榜

更多

创作者周榜

更多

正在热议

更多

# 你现在会用到哪些AI技能？ #

6016次浏览 82人参与

# 蚂蚁求职进展汇总 #

123138次浏览 1163人参与

# 未岚大陆求职进展汇总 #

7408次浏览 84人参与

# 秋招踩过的“雷”，希望你别再踩 #

84804次浏览 1082人参与

# 我对___祛魅了 #

132323次浏览 736人参与

# 大厂VS公务员你怎么选 #

27603次浏览 397人参与

# 平安产险科技校招 #

748次浏览 0人参与

# 你还有多少年退休？ #

26786次浏览 192人参与

# 我的求职进度条 #

90200次浏览 1188人参与

# 实习在多还是在精 #

34966次浏览 243人参与

# 实习下班不想学习，正常吗？ #

20079次浏览 174人参与

# 小马智行求职进展汇总 #

13602次浏览 50人参与

# 你的房租占工资的比例是多少？ #

64831次浏览 798人参与

# 你见过哪些工贼行为 #

16638次浏览 91人参与

# 金蝶求职进展汇总 #

53950次浏览 263人参与

# 总结:哪家公司面试体验感最好 #

70201次浏览 416人参与

# 校招谈薪一定要知道的事 #

13343次浏览 114人参与

# 找工作中的小确幸 #

27074次浏览 278人参与

# 顺丰求职进展汇总 #

63419次浏览 314人参与

# 非技术岗投递进展 #

157972次浏览 1314人参与

# 反问环节如何提问 #

115403次浏览 2463人参与

# 你觉得材料多少算高薪 #

26173次浏览 159人参与

牛客网
牛客网在线编程
牛客网题解
牛客企业服务