UOJ Logo zx2003的博客

博客

关于 UOJ NOI Round #5 Day2T2 一题的其它做法

2021-07-19 22:15:40 By zx2003

这里介绍一个相对通用的办法。

使用重量平衡树(能够保证每个点子树size与自身size只比严格介于 $(c,1-c)$之间的平衡树,$c$ 为取定的常数 )维护序列非0位置。

操作2,3和操作1的区间定位没有影响。

操作1递归访问到的总节点数也不变,唯一问题是信息合并的复杂度。而这满足递归式 $T(n)=T(c*n)+T((1-c)*n)+\log{n}=O(区间长度)$。注意及时清除区间中的0元素。

于是总复杂度仍为 $O(n\log{U}+q\log^2{n})$。

并且我们现在能支持更多操作,比如单点修改权重,对复杂度的影响只有操作1中访问的节点数,均摊代价 $O(\log{U})$;比如序列分裂合并,单次代价与区间定位相同为 $O(\log^2{n})$。

关于重量平衡树,一个OI可写的实现是一种称为 WBLT 的东西。

评论

zx2003
好像这里重量平衡性质不是必要的,因为你可以把修改区间给截出来拍扁成二叉树重构完在接回去,不影响复杂度。
3002xz
orz zx!
Yezc
orz xz!
DPair
orz xz!
leapfrog
orz!

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。