关于线段树合并

学术版

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 16:12:06

@mayike 打一个标记表示将f_{v,1}与f_{v,0} 翻转然后f_{v,1}=\min(f_{v,0},f_{v,1})的标记，然后再区间加

by mayike @ 2024-11-29 16:14:32

@qiuzijin2026 我是这么想的，但是标记下传把我给整懵逼了，遂发此贴

by mayike @ 2024-11-29 16:15:17

@FBW2010@qiuzijin2026 不胜感谢！（~~虽然还是没懂怎么传标记~~

by qiuzijin2026 @ 2024-11-29 16:16:40

@mayike 你其实可以尝试广义矩阵乘法，只需要维护一个乘法标记就可以了

by FBW2010 @ 2024-11-29 16:17:18

@mayike 你写的哪种？矩阵乘法还是直接打标记？

by qiuzijin2026 @ 2024-11-29 16:18:01

@FBW2010 它很明显是直接打标记

by mayike @ 2024-11-29 16:18:02

@qiuzijin2026 @FBW2010 我直接打标记，封闭性转移不了一点

by FBW2010 @ 2024-11-29 16:18:07

@mayike 直接打的话你就直接带进去爆算，套出式子就行了

by mayike @ 2024-11-29 16:19:28

@qiuzijin2026 我也想写矩阵乘法了，感觉根本转移不了，因为它就是跟自己本体（几乎）取min，而其他一些常见可转移的都是前缀之类已知值的

by qiuzijin2026 @ 2024-11-29 16:20:17

@mayike 快试试广义矩阵吧。

f_{i,j}=\min_{k=1}f_{i,k}+f_{k,j}