T3 怎么用树剖+线段树啊
T3 怎么用树剖+线段树啊
不知道线段树怎么维护诶
2019-11-08 18:22 华中科技大学 C++
关注
全部评论
溴溴溴
cdqz
树剖后，每个询问被分成了若干段 形如一个重链的一个区间，和若干个重链的前缀这样。 标程做法如下：前面这部分用线段树搞。后面由于是前缀，所以就预处理前缀的答案，然后对于一个询问，依次扫这些链，同时维护现在的最小值。每次可以找第一个比当前最小值小的点，然后用前缀的答案和当前最小值快速算出答案。标程比较懒，这个地方用了二分，所以总复杂度实际上是O(log^2n)。但是离线一下是可以搞到O(logn)的。（具体就是将询问在每个重链端点按当前最小值排序，每次归并可以维护这个序列）
rprp 楼主
楼主 华中科技大学 C++
Thanks♪(･ω･)ﾉ
溴溴溴
cdqz
在线的话可能没法搞到O(logn)了。。。
相关推荐