zcmimi's blog
avatar
zc
2020-04-15 14:58:00
查看原题

点击跳转

avatar
zc
2020-04-15 13:42:00
查看原题

点击跳转

avatar
zc
2020-04-15 00:06:00
查看原题

点击跳转

avatar
zc
2020-04-13 20:52:00
查看原题

点击跳转

avatar
zc
2020-04-13 20:06:00
查看原题

点击跳转

k-d tree模板

avatar
zc
2020-04-12 15:41:00
查看原题

点击跳转

1 x表示把点x到根节点的路径上所有的点染上一种没有用过的新颜色

从这里可以看出每种颜色在树上都是一条链的形式存在

可以发现这和LCT很像

那么1操作可以看成access操作,(如何操作先放着

x到根的颜色种数也就是要经过的虚边的条数,设为S_x

xy的路径的权值,可以使用树上差分的形式

也就是转化为S_x + S_y - 2\times S_{lca(x,y)} + 1

3操作也就是求子树最值

我们回过头来看access操作:

  1. 原来的实边变虚,意味着要多走一条虚边,将此链所管辖的区域全部+1

  2. 虚边变实边,意味着要多少一条虚边,将此链所管辖的区域全部-1

注意: LCTsplay的父子关系并不是原树中的父子关系,要找到该splay中深度最小的节点(也就是这条链的顶端再操作)

综上可以用 lct+lca+dfs序+线段树 解决

当然也可以通过树剖模拟access的形式来解决

avatar
zc
2020-04-11 22:16:00
查看原题

点击跳转

LCT维护重心

这里利用了两个重心性质:

  1. 树中所有点到某个点的距离和中,到重心的距离和是最小的,如果有两个距离和,他们的距离和一样。

  2. 把两棵树通过某一点相连得到一颗新的树,新的树的重心必然在连接原来两棵树重心的路径上。

我们需要维护子树的大小

合并的时候连接两棵树,分离出连接原来两棵树重心的路径,在链上搜索出答案

方法类似平衡树的查找

avatar
zc
2020-04-10 20:51:00
查看原题

点击跳转

解法一

化边为点

每个点的父边赋予该点的颜色。我们需要两个LCT,每种对应一个颜色。一条边只有在对应颜色的LCT中才会被连上。

接着可以发现,修改一个点的颜色,只需要在原来颜色对应LCT中断开父边,在新颜色LCT中连接父边,就可以维护同色连通块了

查询的时候只要找到x所在splay的根,右子树大小就是答案(相当于边的数目,根的深度最浅,只有右子树)

注意: 1节点是没有父亲的,不过为了模型的建立,要有父边,于是需要加一个虚点,让1的父亲指向它连边

手动模拟一下应该可以懂

avatar
zc
2020-04-09 20:43:00
查看原题

点击跳转

还是QTREE6的方法

从维护子树大小变成了维护子树最值

avatar
zc
2020-04-07 20:04:00
查看原题

点击跳转

fhqtreap做法

在普通fhqtreap的基础上记录节点的父亲

M x y: 一直向上走就可以找到根,然后合并即可

D x: 求出x的排名,然后按排名分裂即可

Q x y: 求出x,y排名,分裂,得出答案,再合并回去

21/73
Search
search