关于线段树合并

学术版

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 mayike @ 2024-11-29 16:21:05

@qiuzijin2026 太甜蜜的好玩了，我要玩广义矩阵！

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

@mayike 取min可转啊，我就这么做的

by FBW2010 @ 2024-11-29 16:21:40

@mayike 看看我的

void work(int k,int p){
    long long x=tree[k].min1,y=tree[k].min2;
    tree[k].min1=min(x+tree[p].a,y+tree[p].b);
    tree[k].min2=min(x+tree[p].c,y+tree[p].d);
    long long a=tree[k].a,b=tree[k].b,c=tree[k].c,d=tree[k].d;
    tree[k].a=min(tree[p].a+a,tree[p].b+c);
    tree[k].b=min(tree[p].a+b,tree[p].b+d);
    tree[k].c=min(tree[p].c+a,tree[p].d+c);
    tree[k].d=min(tree[p].c+b,tree[p].d+d);
}
void pd(int k){
    if(!ls(k))ls(k)=++num;
    if(!rs(k))rs(k)=++num;
    work(ls(k),k);
    work(rs(k),k);
    tree[k].a=tree[k].d=0;
    tree[k].b=tree[k].c=1e15;
}

by mayike @ 2024-11-29 16:21:56

@FBW2010 那就是我太菜了，感觉根本不可转哎。

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

@mayike 翻转取min:

INF,0

0 , 0

原谅我不会打矩阵

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

@mayike 让我手把手教你，先算x

min(min(x+a',y+b')+a,min(x+c',y+d')+c)=min(x+min(a'+a,c'+c),y+min(b'+a,d'+c))

y也同理

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

@qiuzijin2026 漂亮的回旋踢！

by FBW2010 @ 2024-11-29 16:25:15

@mayike 等等，b打成c了

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

@mayike 两种均可，随便你用哪种，能写出来就行

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

@FBW2010 大概差不多就是标记两种目前的下传后的形式，然后再变，pushdown的时候套进去传就可以了，和电路图差不多