林聪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 只会生效这个数量那么多，然后就做完了
查看原帖
点赞 评论
相关推荐
牛客热帖
更多
正在热议
更多
# 我的实习日记 #
3690706次浏览 31880人参与
# 滴滴笔试 #
36757次浏览 208人参与
# 你收到了哪些公司的笔试？ #
1392次浏览 11人参与
# 你认为小厂实习有用吗？ #
125785次浏览 687人参与
# 你现在的工作，是“成长”还是“消耗”？ #
985次浏览 30人参与
# 你上一次加班是什么时候？ #
139122次浏览 776人参与
# 实习进度记录 #
1215902次浏览 11808人参与
# 金三银四，你的春招进行到哪个阶段了？ #
19138次浏览 260人参与
# 2025，我想...... #
91862次浏览 675人参与
# 金融银行面经 #
101323次浏览 551人参与
# 在国企工作的人，躺平了吗？ #
405134次浏览 3966人参与
# 美团笔试 #
706144次浏览 4682人参与
# 小米编程考试 #
32654次浏览 154人参与
# 你听到的“最没用”的秋招建议 #
53930次浏览 326人参与
# AI岗位暴涨12倍，你会转AI赛道吗？ #
6939次浏览 123人参与
# 米哈游笔试 #
561286次浏览 1114人参与
# 秋招报数：你投了多少家公司？ #
157252次浏览 959人参与
# 字节7000实习来了，你投了吗？ #
6446次浏览 34人参与
# 职场上哪些行为很加分？ #
338164次浏览 3752人参与
# 今天你投了哪些公司？ #
200253次浏览 3407人参与