2023-09-07 23:03 河南大学 C++
关注
携程笔试9.7
贴一个t4的做法：维护前缀和，遇到0加一，遇到1减一。对于每一个左端点来说，合法的右端点是这个区间的前缀和值都大于等于左端点的前缀和值。因此考虑记录每一个位置的前缀和值，查询时二分找到左端点的第一个小于左端点的前缀和值的位置，减一下就得到对应的区间对答案的贡献。时间复杂度O(nlogn)。
全部评论
runningcake_
中国人民大学 算法工程师
这个 s = " " + s 学到了
JoseKnife
门头沟学院 Java
请教一下：`查询时二分找到左端点的第一个小于左端点的前缀和值的位置` 前缀和数组不是升序数组，是怎么通过二分找到的？
牛客281421101号
北京航空航天大学 Java
我直接把前缀数组所有项加起来就过了，没二分查找
相关推荐
03-28 00:43
杭州电子科技大学 C++ 
找工作勤劳小蜜蜂：矛盾是没有实习，就是没实战经验，公司不想要，公司不要，你就没有实习，你就进入死循环，另外你的项目不是社会现在有大量岗位存在行业用的，云存储人员早就饱和。 点赞 评论 收藏
分享
点赞 评论 收藏
分享