菜菜,搞不清楚。
标记的含义
意思就是你写了个有标记的线段树,但标记下传时如果需要使用一些数据结构上的信息,它使用的到底是什么。
此时使用的信息,是打标记时的(之前的),而不是当前的,我之前一直没考虑过这一点。所以我们下传此标记时应该使用的是原来下传前的节点信息,然后正常玩就行。
明明是正常操作,为啥这么麻烦捏?因为即使在标记下传前不会访问到它的儿子,但它身上别的标记可能发生更改,比如这个标记的下传需要使用区间加标记,但区间加标记此时从他父亲合并到了他身上,这样你下传此标记(此时这个标记也会由一堆不同时间的标记合并而来)的时候就分不清楚它应使用的是哪一部分区间加标记,这需要我们用一些手段来分清当前的信息是啥。
最值操作转化为最值加
比如区间对 取 ,在节点上维护区间最大值 和次大值 ,那么 对区间无影响, 等同于将所有区间最大值改为 。这个标记也是带有时间的(更改当前状态下数据结构中的区间最大值),下传时我们应该在别的标记下传前下传到最大值较大的儿子就行,这样就去除了后来打在自己身上的标记的影响。
跟这个比较像的有 CF997E 中的一部分,就是:区间加,统计区间内历史 的总出现次数,保证序列任何时刻非负。维护一个标记 表示对区间内的 加贡献,然后下传的时候就不难理解为什么不是挑 下传而是挑较小的下传了。当时我比较菜,在这疑惑了一年。
历史最值
就比如说区间加 。假设线段树上维护历史最值 ,对这个区间加了之后,要做的事情是将子树内所有节点的 对其当前时刻的 取 。现在考虑进后来的区间加标记,发现对答案有贡献的只有一个时刻,就是从上次下传到这次下传之前,区间加标记增到最大的那个时刻。所以我们维护一个 表示从上次下传标记到现在,该节点的区间加标记达到的最大值,然后更新 时用 来代替区间加标记就行了。
历史版本和
维护一次函数是好的并且没有任何坏处。
施工中