第一题 预处理一个数组为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

相关推荐

神哥了不得:放平心态,再找找看吧,主要现在计算机也变卷了,然后就比较看学历了,之前高中毕业你技术强,都能找到工作的
点赞 评论 收藏
分享
01-07 07:54
已编辑
门头沟学院 前端工程师
点赞 评论 收藏
分享
点赞 评论 收藏
分享
牛客网
牛客企业服务