在 Codeforces 上看了一些新姿势,但还不是很懂,先备份一下
[[1]Efficient and easy segment trees](http://codeforces.com/blog/entry/18051)
[[2]Non-recursive Implementation of Range Queries and Modifications over Array](http://codeforces.com/blog/entry/1256)
注意他们用的是左闭右开区间,我们的zkw用的是全开……

总体说来比我平时实现的 zkw 多了一些良好的特性

  • 空间非强制2的幂
  • 支持懒标记(要维护点到根的前缀和,代码还没看懂……)

懒标记真没懂啊……
[1]中用d[]维护当前点tag,t[]维护当前点和;每次modify()的时候两端点从根push()下来到全部结点,然后处理完后再build()上去。
这里一个疑问就是build()只对直系祖先进行更新,而被修改结点不在端点的直系祖先里啊……他们的祖先没有更新到啊……

[UPD]懂了懂了。这两次build()保证了所有标记的最顶上的节点的父亲会被更新到。往上均是正确的标记,而每次query()push()会将这些还未向下更新的标记下推并更新,正确性得到!

这样一来有标记下传就无需标记永久化了~没有了普通zkw标记必须满足无覆盖性的要求~
欸等等push()真的不是 $ O(|r-l|)=O(n) $ 的吗!????

[UPD]想了一中午,感觉可以这么做:
考虑各标记之于待查询区间的关系。
1° 完全被待查询区间包含:结点值已是最近,毋需下推。
2° Otherwise: 注意到结点所用到统计的量的结点是左右端点直系祖先的兄弟节点。只对左右祖先到根的链从上到下进行下推即可,就可以保证复杂度为$ O(\lg n) $了。

啊啊不太想特别去实现呢~遇到题再说吧~

标签: zkw

添加新评论