林聪123
2025-08-16 21:34 西安电子科技大学 C++
关注
第三题我的想法是离散化后维护正序对数组，本质上题目要求的就是对于每个 i，i 右侧的正序对数量，但正序对需要满足一个前提是不能超过 a[i]。
所以逆序遍历，维护一个 f[x] 表示截至目前为止，正序对最大值为 x 的正序对数量，那么遍历到 i 的时候，此时的贡献就是 f 数组的 1 ~ a[i] - 1 这一段的区间求和，因为这一段的正序对就没超过 a[i]。
接着就是要更新 f 数组，也就是说要把 a[i] 也给***去，插的时候比较直观的就是 a[i] 会对 a[i] + 1 ~ n 这一段产生贡献，也就是对这一段区间 +1，但问题是这一段有的点还不存在，那么是没有贡献的，所以我们在线段树上维护一个“节点打开数量”，初始所有节点都是“关闭”的，每次打开一个新的点，然后因为维护了这个数量，所以区间 +1 对区间 sum 只会生效这个数量那么多，然后就做完了
查看原帖
点赞 评论
相关推荐
03-31 17:40
门头沟学院 算法工程师 
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 这个offer值得去吗？ #
38876次浏览 250人参与
# 工作压力大，你会干什么？ #
81878次浏览 703人参与
# 在爱玛，骑向未来 #
43401次浏览 431人参与
# 如果春招能重来，我会___ #
32685次浏览 320人参与
# 什么专业适合考公 #
69131次浏览 336人参与
# 除了线上，还能去哪些地方投简历 #
17647次浏览 147人参与
# 机械人，说说你的烦心事 #
147969次浏览 1158人参与
# 工作后，你落下了哪些病根 #
42114次浏览 292人参与
# 携程笔试 #
173644次浏览 916人参与
# 毕业季，给职场新人一些建议 #
220609次浏览 2595人参与
# 职场新人体验 #
192402次浏览 1239人参与
# 你上一次加班是什么时候？ #
157175次浏览 822人参与
# 你被哪些公司挂了？ #
197277次浏览 1074人参与
# 选offer应该考虑哪些因素 #
172130次浏览 1054人参与
# 机械人，秋招第一次笔试的企业是哪家？ #
103153次浏览 704人参与
# 你觉得哪一届的校招最难？ #
440569次浏览 3261人参与
# 听到哪句话代表面试稳了OR挂了？ #
156352次浏览 838人参与
# 记录我的毕业季 #
6215次浏览 149人参与
# 你觉得技术面多长时间合理？ #
187330次浏览 1226人参与
# 来聊聊你目前的求职进展 #
765340次浏览 7053人参与
# 华为池子有多大 #
179322次浏览 938人参与