• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

势能线段树浅析

开发技术 开发技术 4小时前 1次浏览

势能线段树其实就是对于一些数据结构题,我们察觉到其中存在一些规律:

一段区间或某个点的修改次数不会超过 (k) 次, (k) 的值很小或为一个常数。

这样我们就可以在这个点修改了 (k) 次之后让它不再修改。

详解可见 link 。

这里我们转载一下其中最重要的几句话:

我们知道,线段树能够通过打标记实现区间修改的条件有两个:

  1. 能够快速处理标记对区间询问结果的影响 。

  2. 能够快速实现标记的合并 。
    但有的区间修改不满足上面两个条件(如区间开方,区间取模等)。

但某些修改存在一些奇妙的性质,使得序列每个元素被修改的次数有一个上限。

可以在线段树每个节点上记录一个值,表示对应区间内是否每个元素都达到修改次数上限。

区间修改时暴力递归到叶子节点,如果途中遇到一个节点,这个节点的对应区间内每个元素都达到修改次数上限则在这个节点 (return) 掉 。

可以证明复杂度为 (O ( nlogn×) 修改次数上限())

推荐题目:

P4145 上帝造题的七分钟 2 / 花神游历各国

CF438D The Child and Sequence

CF920F SUM and REPLACE


程序员灯塔
转载请注明原文链接:势能线段树浅析
喜欢 (0)