标签 zkw 下的文章

拓展zkw

  • 时间:
  • 分类:
  • 评论

在 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) $了。

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