数据结构/大模拟易错提醒

· · 个人记录

1. 线段树多标记合并 (max)。

我们考虑这样的结构：区间加，区间取 \max，区间最大值。

显然维护加标记和取 \max 标记。

取 \max 标记对加标记没有影响，而加标记对取 \max 标记有加的影响，这个不能忘记。

这里没有查区间和，不需要吉司机线段树，只有说区间取 \max 或 \min 操作，同时需要区间加的时候才需要吉司机。吉司机注意势能即可，记录一个最大值/次大值即可。

2. 主席树区间加应该如何维护

如果没有区间询问，可以直接使用永久化标记的做法，注意还是要继承节点的所有信息。

考虑有区间询问怎么写？发现难点在于懒标记下传。

由于每个节点都可能直接指向别的人的儿子，那么 ori 的儿子不一定是 ori 本身的儿子，有可能也是接前面的，所以所有标记下传都要开新点。

当 A<=l&&r<=B 的时候，注意此时当前点的信息是相对原来的发生了改变，所以要继承其信息。注意这里继承要把 ls 和 rs 都计入。不要只计入 maxn 或 sum。

同理，down 的时候也要注意所有信息都要继承。并且要注意，如果原点没有这个信息，则不继承直接创建，否则继承。

具体看这两条评测记录：

60 pts

100 pts