zcmimi's blog

arrow_back线段树合并共3篇文章

avatar
zc
2020-03-02 02:05:00
查看原题

点击跳转

线段树合并的时候取\min(\text{交换前},\text{交换后})

avatar
zc
2020-03-01 19:36:00
查看原题

点击跳转

先离散化权值为排名,从大到小排序

遍历所有点,用权值树状数组统计,结果是 遍历完该子树后答案 - 遍历该子树前答案

(为什么一开始会去想什么dsu on tree和线段树合并

avatar
zc
2020-03-01 14:52:00
查看原题

点击跳转

树上差分,统计的时候每个节点都合并自身子节点的结果

每个点都维护一颗动态开点权值线段树

x\leftrightarrow y区间加可以看成x,yw位置+1,lca(x,y),f_{lca(x,y)}w位置-1

统计的时候不断向上线段树合并

具体看代码

1/1
Search
search