关于线段树合并

学术版

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:46:13

@mayike 直接打个取min标记不就行了

by 729hao @ 2024-11-29 15:46:24

@mayike 运用标记的封闭性

by bs_commander @ 2024-11-29 15:47:03

使用矩阵乘法补位

by mayike @ 2024-11-29 15:49:04

@qiuzijin2026@729hao@bs_commander %%%是要打标记，没想好过程

by qiuzijin2026 @ 2024-11-29 15:51:57

@mayike 区间加与将1与0取min的标记。

min(x+a,b)+c=min(x+(a+c),b+c)

min(min(x+a,b),c)=min(x+a,min(b,c))

by FBW2010 @ 2024-11-29 15:53:14

@mayike 一维为什么要线段树 >

by mayike @ 2024-11-29 15:54:44

@qiuzijin2026 但由于 f_{v,0/1} 并不能直接得到实际值，所以更新不了 min，卡在这点了

by mayike @ 2024-11-29 15:55:14

@FBW2010 假设还有一维

by FBW2010 @ 2024-11-29 15:56:13

@mayike 假设是指的哪一维？请说清楚点

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

@FBW2010 f_{u,q,0/1}，中间加了个 q，所以才要线段树

| 下一页