关注
离散化后维护正序对数组,本质上题目要求的就是对于每个 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 只会生效这个数量那么多,然后就做完了。
查看原帖
点赞 评论
相关推荐
点赞 评论 收藏
分享
点赞 评论 收藏
分享
牛客热帖
更多
- 1... 工作半年后更确定:我们依然不欠优绩主义什么6733
- 2... 我建了一个分享实习业务的仓库,欢迎大家贡献哦2527
- 3... 岁末论道:谁才是牛客 2025 最强修仙者?2398
- 4... #牛客2025仙途报告#居然是五颗星2270
- 5... 【2025-年终总结】25届毕业生果果牛这一年~1962
- 6... 一个程序员的自救书|从酒吧陪玩DM到上岸大厂1803
- 7... 仙途报告1780
- 8... 腾讯 微信支付一面面经1772
- 9... 28第二次面试1326
- 10... 在当下这个社会,在人生这个无常的时代,我真心希望你和各位牛友开心1209
正在热议
更多
# 牛客2025仙途报告 #
10723次浏览 220人参与
# 我们是不是被“优绩主义”绑架了? #
1205次浏览 53人参与
# 2025年终总结 #
190225次浏览 3201人参与
# 找工作,行业重要还是岗位重要? #
86856次浏览 1736人参与
# 你面试体验感最差/最好的公司 #
27322次浏览 455人参与
# 今年你最想重开的一场面试是? #
10296次浏览 119人参与
# 礼物开箱Plog #
2832次浏览 99人参与
# 为了秋招你都做了哪些准备? #
29469次浏览 524人参与
# 一人说一个提前实习的好处 #
19582次浏览 287人参与
# 秋招落幕,你是He or Be #
20830次浏览 362人参与
# 机械人晒出你的简历 #
147829次浏览 883人参与
# 重来一次,你会对开始求职的自己说 #
9337次浏览 234人参与
# 工作中听到最受打击的一句话 #
11548次浏览 169人参与
# 实习没事做是福还是祸? #
22241次浏览 328人参与
# 工作两年,想和老板谈涨薪怎么说 #
39058次浏览 176人参与
# 离家近房租贵VS离家远但房租低,怎么选 #
13903次浏览 130人参与
# 25届暑期实习 #
1039137次浏览 20592人参与
# 实习的内耗时刻 #
212571次浏览 1579人参与
# 拿到offer之后,可以做些什么 #
81345次浏览 431人参与
# 这些公司卡简历很严格 #
82616次浏览 375人参与