携程笔试9.7

贴一个t4的做法：维护前缀和，遇到0加一，遇到1减一。对于每一个左端点来说，合法的右端点是这个区间的前缀和值都大于等于左端点的前缀和值。因此考虑记录每一个位置的前缀和值，查询时二分找到左端点的第一个小于左端点的前缀和值的位置，减一下就得到对应的区间对答案的贡献。时间复杂度O(nlogn)。
全部评论
这个 s = " " + s 学到了
1 回复 分享
发布于 2023-09-07 23:49 北京
请教一下：`查询时二分找到左端点的第一个小于左端点的前缀和值的位置` 前缀和数组不是升序数组，是怎么通过二分找到的？
点赞 回复 分享
发布于 2023-09-10 21:03 上海
我直接把前缀数组所有项加起来就过了，没二分查找
点赞 回复 分享
发布于 2023-09-08 13:45 江西

相关推荐

07-11 08:18
北京科技大学 C++
点赞 评论 收藏
分享
昨天 18:09
门头沟学院 Java
点赞 评论 收藏
分享
06-11 22:00
西南交通大学 嵌入式硬件工程师
佬们求康康
各位大佬帮我看看简历呗😊，现在真纯混子了，写的都是一些校内课程项目，打算根据这些恶补知识，不知道这样到校招够不够找到一些工作😂
zYvv：双一流加大加粗再标红，然后广投。主要是获奖荣誉不够，建议开始不用追求大厂，去别的厂子刷下实习。
点赞 评论 收藏
分享
06-21 01:03
门头沟学院 Java
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-09 12:02
活久见，遇见真boss了
ssob上原来真有BOSS啊
硫蛋蛋：这种也是打工的，只不是是给写字楼房东打工
点赞 评论 收藏
分享
评论
6
9
分享

全站热榜

更多

创作者周榜

更多
正在热议
更多
# 如何提高实习转正率？ #
3186次浏览 51人参与
# 你后悔自己读研吗？ #
2412次浏览 83人参与
# 大厂面试初体验 #
7307次浏览 47人参与
# 月薪多少能在一线城市生存 #
3076次浏览 81人参与
# leader认为你工作不认真怎么办 #
31234次浏览 147人参与
# 如果公司给你放一天假，你会怎么度过？ #
17241次浏览 129人参与
# 选完offer后，你后悔学本专业吗 #
47462次浏览 237人参与
# 三一重工求职进展汇总 #
15241次浏览 68人参与
# 离家近房租贵VS离家远但房租低，怎么选 #
9197次浏览 119人参与
# 我的国央企投递进展 #
46850次浏览 294人参与
# 总结:哪家公司面试体验感最差 #
61202次浏览 276人参与
# 最难的技术面是哪家公司？ #
1183次浏览 21人参与
# 机械人，你被简历秒挂的企业有哪些？ #
43113次浏览 281人参与
# 投递几十家公司，到现在0offer，大家都一样吗 #
246514次浏览 1792人参与
# 拼多多工作体验 #
29203次浏览 199人参与
# 你认为哪些项目算烂大街？ #
1292次浏览 35人参与
# 如果可以，你希望哪个公司来捞你 #
101696次浏览 469人参与
# 你以为的实习VS真实的实习 #
1467次浏览 30人参与
# 职场上哪些事情令人讨厌 #
19086次浏览 92人参与
# 国企是理工四大天坑的最好选择吗 #
13814次浏览 95人参与
牛客网
牛客网在线编程
牛客网题解
牛客企业服务