zcmimi's blog
avatar
zc
2020-04-16 18:02:00
查看原题

点击跳转

首先: 构建KDT

对每个点分别进行查询,也就是搜索

直接对KDT进行遍历每次搜索的复杂度是O(n)的,显然TLE

这时我们需要估价函数,在这里也就是:

估算出查询点到子树对应的长方形中的点的"最近距离"

若"最近距离"已经超过了当前答案,就跳过当前子树.

搜索时比较左右子树的"最近距离",先搜索"最近距离"小的

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的方法

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

22/74
Search
search