严格的摸鱼查询题解

考虑暴力覆盖，复杂度可能会到O(n^2)级别。
实际上，暴力覆盖最多覆盖O(n)级别的位置，很多位置被重复覆盖了。
可以采用线段树来记录一个区间是否被全部覆盖过，但是这样做并不是很简单，我们可以采用其他的方法。
在记录覆盖的时候，覆盖过的位置记录为从此位置开始，最右端被覆盖过的位置是哪里。
这样暴力的时候就可以直接跳。
复杂度变成了总的O(n)级别，因为每个位置最多被覆盖1次，总的复杂度也就是O(n)级别了。

全部评论

相关推荐

头像 会员标识 头像
YUKARI_
05-09 07:34
已编辑
深言科技_大模型数据_数据开发(实习员工)
暑期实习：杀不死你的都只能让你更加强大
3月：整整投+面了一个月 腾讯笔试，饿了么笔试，蚂蚁笔试都做的稀烂，做完秒挂；东子面完直接关闭实习生通道了；团子做的还行结果一面死；百度二面稀烂，答的我都想直接关电脑走人了；NV官网显示被拒了；   焦虑吗？真的很焦虑。但是清明节还是决定出去玩 认认真真玩了四天回来之后，美团重新复活了，NV也复活了，百度也复活了。   四月，一个月前一无所有的我，收到了团子的Offer，然后陆续收到了上述公司的Offer。四月，一个月前笔试稀烂的我，拿到了第一个笔试的AK， 然后是更多的笔试AK。&nbs...
投递饿了么等公司10个岗位 > 第一次面试 我的求职思考
点赞 评论 收藏
转发
头像
牛客119763290号
05-09 21:26
已编辑
西安交通大学 计算机类
offer极限二选一！
科大讯飞消费者bg二级研究院 语音算法岗 24k*14
点赞 评论 收藏
转发
头像
Machine77
03-28 20:10
门头沟学院 计算机类
点赞 评论 收藏
转发
头像 头像
conghuhu
昨天 17:24
字节跳动_抖音_后端研发(准入职员工)
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议
# 牛客帮帮团来啦！有问必答 #
710691次浏览 11528人参与
# 许愿池 #
77222次浏览 1542人参与
# 通信硬件人笔面经互助 #
107798次浏览 2178人参与
# 你的秋招进展怎么样了 #
501051次浏览 13425人参与
# 找工作时遇到的神仙HR #
177690次浏览 1744人参与
# 如何写一份好简历 #
259391次浏览 3918人参与
# 铜五铁六真的存在吗？ #
27365次浏览 293人参与
# 找工作，你会甘心进小厂还是猛冲大厂 #
35074次浏览 352人参与
# 产品实习，你更倾向大公司or小公司 #
35959次浏览 548人参与
# 非技术岗是怎么找实习的 #
73881次浏览 1385人参与
# 市场营销面经 #
4559次浏览 125人参与
# 互联网公司评价 #
79597次浏览 1087人参与
# 通信硬件薪资爆料 #
196352次浏览 1759人参与
# 你的秋招进行到哪一步了 #
353102次浏览 6269人参与
# 硬件兄弟们 甩出你的华为奖状 #
27522次浏览 180人参与
# 无实习如何秋招上岸 #
224756次浏览 3518人参与
# 投了多少份简历才上岸 #
56712次浏览 947人参与
# 面试中的破防瞬间 #
82593次浏览 1015人参与
# 通信/硬件的薪资开多少，才值得去？ #
10746次浏览 140人参与
# 产品人求职现状 #
50605次浏览 747人参与
牛客网
牛客企业服务