zcmimi's blog

arrow_back并查集共21篇文章

avatar
zc
2020-10-29 16:00:01

查看原题

点击跳转

可以想到用并查集维护连通块(需要数字相同区域)个数

答案就是9*连通块个数

直接对每个点维护普通的并查集太慢了

由于并查集是可以合并的,我们可以使用倍增来合并

将一个点拆成\log n个点,分别代表从点i开始长度为2^k的子串

那么当我们处理两个区间相等的关系时,对区间做二进制拆分,拆成log个区间,分别并起来即可

最后再从上(大)往下(小)连边

avatar
zc
2020-10-15 22:15:41

查看原题

点击跳转

首先可以用并查集判断每个1操作是否有效

接下来很容易可以想到树剖+线段树优化建图

很可惜,出题人卡了这种大常数做法

考虑直接在树上倍增优化建图

和倍增lca差不多,一直向上连边

而每个点又拆为入点和出点

每次构建传送门时新建一个点,

连边时只需要[u_1,v_1]所在的块出点连接新建点,新建点连接[u_2,v_2]所在的块入点

详细见代码

avatar
zc
2020-09-14 16:15:00
查看原题

点击跳转

题意: 给一颗树,每条边权值可以修改为x,使得修改后这条边可以在最小生成树上,问x最大可以是多少?

首先求出最小生成树(以下的树指最小生成树)

修改一条边时,若不是最小生成树上的边,则为树上该边两端节点之间的最大值

若是树上的边,那么就是该边子树中找出一些非树边(使它们最大值尽可能小)连接除子树部分的点,答案为该边权值

看上去不是很好处理

我们将非树边按权值从小到大排序,从下往上合并,用并查集维护即可

每次遇到非树边x,y时,就更新并合并x\to \text{lca}_{x,y},y\to \text{lca}_{x,y},从下往上跳时,并查集可以跳过已经打过标记的边

详见代码

avatar
zc
2020-07-25 23:00:00
查看原题

点击跳转

题意:

给出n个点m条边的无向图,每条边u\leftrightarrow v有两个权值a,b

q个询问,给出u,v,A,Bu,v间是否存在路径\max\{a\}=A\max\{b\}=B

先考虑最暴力的做法:

把所有符合条件的边(a\le A,b\le B)添加到并查集,

然后判断最大值是不是A,Bu,v是否连通

接着对边排序、回滚莫队,使用按秩合并并查集(可撤销并查集)

m条边按a进行排序

对询问按b进行排序

m条边进行分块

对每个块处理符合a大于等于该块\max\{a\}的询问

把当前块前面的点按照b排序(使b单调递增)

开始处理询问:

当前块前面的点的b是单调递增的,而a一定符合条件 ,所以可以一直右移指针添加符合条件的边

然后枚举块中的边,添加符合当前询问的边,得到当前询问答案,回滚,删掉当前询问添加的边

下一个询问

处理完当前块后,暴力清空并查集

分块大小为\sqrt{m\log n}时复杂度最优

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

点击跳转

先了解[WC2011]最大XOR和路径的做法

线段树分治+并查集+线性基

加边删边可以用按秩合并的并查集解决,遇到环就插入线性基

由于并查集无法删除元素,删边可以用线段树分治处理(转化为每条边在一个时间段存在)

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

点击跳转

要转化为加边,之后用并查集维护是否连通就可以了(带权维护连通块大小,为n的时候说明全部连通)

每条边都在特定的时间段中出现

由于加边完还要删掉这里使用按秩合并

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

点击跳转

LCT维护重心

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

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

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

我们需要维护子树的大小

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

方法类似平衡树的查找

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

点击跳转

fhqtreap做法

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

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

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

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

avatar
zc
2020-01-19 14:13:00
查看原题

点击跳转

我们可以把每对x,y都看成边

如果当前x,y已经连通,那么当前客人一定会悲伤(相当于加上x\leftrightarrow y后形成了环,显然没法实现)

那么答案+1

可以用并查集实现

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

枚举哪些行和哪些列要变成回文

处理:

行:点(i,j)对应点(i,m-j+1)

列:点(i,j)对应点(n-i+1,j)

我们可以用并查集合并这些点

然后求每个块中0还是1多

1/3
Search
search