关于线段树合并

学术版

mayike @ 2024-11-29 15:39:47

在遇到这种转移：

f_{u,0}=\sum_{v\in son_u} f_{v,1}

f_{u,1}=a_u+\sum_{v\in son_u}\min(f_{v,0},f_{v,1})

第二种的 \min(f_{v,0},f_{v,1}) 在线段树合并时怎么转移啊

by qiuzijin2026 @ 2024-11-29 15:58:21

@mayike merge时，传一下特殊值以外的普通值。在有一个节点为空时，对另一个节点，打标记即可

by mayike @ 2024-11-29 16:00:29

@qiuzijin2026 准确来讲我的方法是新开节点，也就是说无儿子的节点的权值都是一样的，但是...我太菜了啊啊啊啊啊啊啊啊

by FBW2010 @ 2024-11-29 16:01:00

@mayike 合并时考虑u子树为空和v子树为空的情况，分别要一个 x,y->x+a,y+b 和 x,y->y,min(x,y) 的操作，用标记的封闭性推推式子，可以化成 min(x+a,y+b),min(x+c,y+d) 的形式。化的过程就不列出来了

by mayike @ 2024-11-29 16:03:12

@FBW2010 那请问一下在没有 x 这个值的时候怎么打标记 y\gets \min(x,y) 啊？

by mayike @ 2024-11-29 16:03:42

@FBW2010 说错了，就是 x 的值在底层还未被获取

by qiuzijin2026 @ 2024-11-29 16:04:37

@mayike 传一般值就行了

by qiuzijin2026 @ 2024-11-29 16:05:54

@mayike 它的值不是没有时都一样吗，你把这个值传进去就行了呀

by FBW2010 @ 2024-11-29 16:06:31

@mayike 什么东西？怎么会没有值呢

by mayike @ 2024-11-29 16:08:04

@qiuzijin2026 我目前不会的是 u 的值一样，要往 v 传的情况。即：

f_{v,0}=f_{u,0}+f_{v,1}

f_{v,1}=f_{u,1}+\min(f_{v,0},f_{v,1})

然后返回 v 节点的情况

by FBW2010 @ 2024-11-29 16:09:16

@mayike 那就是v变成 y,min(x,y)，xy表示0和1的状态，然后加上u子树里的就行了