T3 怎么用树剖+线段树啊

T3 怎么用树剖+线段树啊
不知道线段树怎么维护诶

全部评论
树剖后,每个询问被分成了若干段 形如一个重链的一个区间,和若干个重链的前缀这样。 标程做法如下:前面这部分用线段树搞。后面由于是前缀,所以就预处理前缀的答案,然后对于一个询问,依次扫这些链,同时维护现在的最小值。每次可以找第一个比当前最小值小的点,然后用前缀的答案和当前最小值快速算出答案。标程比较懒,这个地方用了二分,所以总复杂度实际上是O(log^2n)。但是离线一下是可以搞到O(logn)的。(具体就是将询问在每个重链端点按当前最小值排序,每次归并可以维护这个序列)
1 回复
分享
发布于 2019-11-10 00:18
在线的话可能没法搞到O(logn)了。。。
点赞 回复
分享
发布于 2019-11-10 00:19
小红书
校招火热招聘中
官网直投
Thanks♪(・ω・)ノ
点赞 回复
分享
发布于 2019-11-10 18:23

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务