溴溴溴
2019-11-10 00:18 cdqz
关注
树剖后，每个询问被分成了若干段 形如一个重链的一个区间，和若干个重链的前缀这样。 标程做法如下：前面这部分用线段树搞。后面由于是前缀，所以就预处理前缀的答案，然后对于一个询问，依次扫这些链，同时维护现在的最小值。每次可以找第一个比当前最小值小的点，然后用前缀的答案和当前最小值快速算出答案。标程比较懒，这个地方用了二分，所以总复杂度实际上是O(log^2n)。但是离线一下是可以搞到O(logn)的。（具体就是将询问在每个重链端点按当前最小值排序，每次归并可以维护这个序列）
查看原帖
1 评论
相关推荐
点赞 评论 收藏
分享
点赞 评论 收藏
分享
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 为了入行xx岗，我学了__ #
7533次浏览 116人参与
# 26届校招投递进展 #
586615次浏览 3775人参与
# 简历第一个项目做什么 #
8634次浏览 126人参与
# 被说“做题家”，你的反应是_____？ #
3280次浏览 106人参与
# 参加哪些竞赛对找工作有帮助？ #
9686次浏览 150人参与
# 你都见过什么样的草台班子？ #
10993次浏览 86人参与
# Prompt分享 #
3618次浏览 98人参与
# 找实习记录 #
41834次浏览 598人参与
# 工作压力大，你会干什么？ #
15640次浏览 336人参与
# 从哪些方向判断这个offer值不值得去？ #
48781次浏览 342人参与
# 找工作前vs找工作后的心路变化 #
37332次浏览 301人参与
# AI让你的思考变深了还是变浅了？ #
6134次浏览 149人参与
# 多益网络求职进展汇总 #
62311次浏览 281人参与
# 如果不上班，你会去做什么 #
8677次浏览 298人参与
# 入职以后才知道的校招谎言 #
117314次浏览 747人参与
# 去年你投递实习了吗？ #
28244次浏览 335人参与
# 大家每天通勤多久？ #
75517次浏览 537人参与
# 今年秋招还有金九银十吗 #
71483次浏览 502人参与
# 邪修省钱套路 #
8704次浏览 268人参与
# 校招入职后的感受 #
466760次浏览 3629人参与