关注
第一题
预处理一个数组为p数组pi表示i + a[i] - 1;表示以i为最左侧,能够扩展到的最右边界。
然后遍历1-n,在i位置,找到以i为右边界,区间[1, i - 1]选一个作为左边界满足的个数。
那么每个在i位置的贡献就为 a[i] + sum(p[j] >= i) (j ∈ [1, i - a[i]]) 。
sum(p[j] >= i) 表示j所在区间中,p[j] >= i 的个数。这个值可以用树状数组快速计算得出。
时间复杂度为O(nlogn)。
1
相关推荐
点赞 评论 收藏
分享
点赞 评论 收藏
分享
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 笔试 #
2032961次浏览 23168人参与
# 互联网回暖,腾讯要招5000人! #
6140次浏览 90人参与
# 元戎现在香不香 #
64952次浏览 529人参与
# 牛友故事会 #
170072次浏览 2865人参与
# 技术岗笔试题求解 #
25414次浏览 386人参与
# 金融银行面经 #
60678次浏览 482人参与
# 腾讯2025实习生招聘 #
16444次浏览 649人参与
# 两会劳动法放大招 #
28310次浏览 478人参与
# 双非应该如何逆袭? #
23563次浏览 822人参与
# bilibili求职进展汇总 #
42719次浏览 443人参与
# 安克创新求职进展汇总 #
20046次浏览 158人参与
# 应届生应该先就业还是先择业 #
84133次浏览 498人参与
# 投格力的你,拿到offer了吗? #
63493次浏览 502人参与
# 我的省钱小妙招 #
5492次浏览 168人参与
# 24届通信硬件秋招薪资爆料 #
75502次浏览 428人参与
# 电网笔面经互助 #
28378次浏览 294人参与
# 能让你振作起来的一句话 #
43261次浏览 365人参与
# 你投递的公司有几家约面了? #
57137次浏览 415人参与
# 如果中了500万,你会离职吗? #
59216次浏览 438人参与
# 网易有道工作体验 #
4886次浏览 19人参与
# 生物制药/化工公司爆料 #
14426次浏览 65人参与
# 我想象的实习vs现实的实习 #
261645次浏览 2105人参与