blueswiller
2025-03-15 21:11 华南理工大学 算法工程师
关注
给出一个做法，刚刚才想到，应该没问题，时间复杂度为 O(max(30n, nlogn)): 1. 根据 0 切分数组。2. 现在问题转化为>=1 的情况，我们首先维护每一个数前一个 > 1 的数的位置，同时维护一个长度的差分数组，初始值全为 0。3. 我们从每一个数 i 开始向前跳，至多跳 30 次，维护这个过程中的乘积，于是得到 30 个区间加和。举例：假设从 j1 跳到 j2 ，相当于对查询长度 (i- j1 + 1) 至 (i - j2) 贡献 a_i * ... * a_j1。4. 对于所有区间加和，我们采用差分数组结合树状数组对其进行维护，由于长度至多为 n ，树状数组构建的复杂度为 O(nlogn)，于是，构建阶段的复杂度为 O(max(30n, nlogn))。在线单次查询的复杂度为树状数组查询的复杂度 O(logn)。
查看原帖
4 4
相关推荐
点赞 评论 收藏
分享
01-09 17:20
门头沟学院 前端工程师 
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 牛客新年AI问运 #
12045次浏览 155人参与
# 实习教会我的事 #
59489次浏览 454人参与
# 牛客AI体验站 #
17522次浏览 298人参与
# 最难的技术面是哪家公司？ #
66223次浏览 982人参与
# 当你面对裁员会如何？ #
366979次浏览 2923人参与
# 一张图晒一下你的AI员工 #
14167次浏览 177人参与
# 职场上哪些行为很加分？ #
327975次浏览 3634人参与
# 找不到实习会影响秋招吗 #
1447246次浏览 13730人参与
# 哪些公司对双非友好 #
208020次浏览 1169人参与
# 找实习是选平台还是选业务？ #
45303次浏览 317人参与
# 这份实习，有没有动摇过你的职业方向？ #
1527次浏览 20人参与
# 实习怎么做才有更好的产出 #
33031次浏览 417人参与
# 面试之前应该如何准备？ #
219494次浏览 2330人参与
# 第一次面试 #
1073276次浏览 13740人参与
# 工作中，努力重要还是选择重要？ #
261899次浏览 2475人参与
# 九月了，是考研还是就业？ #
88635次浏览 547人参与
# 拿到offer之后，可以做些什么 #
90812次浏览 460人参与
# 24秋招避雷总结 #
940863次浏览 7034人参与
# 有必要和同事成为好朋友吗？ #
2069次浏览 38人参与
# 如果再来一次，你还会选择这个工作吗？ #
814977次浏览 6421人参与