并查集的第二次总结
不知道为啥突然就想做并查集了。于是找来一大堆题目做了2天。
下面的题目分析，数据范围似乎不是那么准确。随意好了。
复杂度分析
在UOJ的群里面发了一个势能分析的课件。看了不是很懂。不过几个结论倒还是记住了。
启发式合并
在合并的时候把大小较小的块并入较大的块。只有较小的块路径+1了，较小的块的size<<=1了。
由于只会并入logn次，于是复杂度变为了O(nlogn)。
按秩合并
在合并的时候把秩较小的块并入秩较大的块。根节点秩+1 当且仅当 两个块根节点秩相同。
所以最后复杂度参见2048小游戏。
路径压缩
根据UOJ的某课件，路径压缩的势能分析得到的复杂度为O(nlogn)。
（我还是想尝试去弄懂一下势能分析来着）
完全体
根据UOJ的某课件，完全体的势能分析得到的复杂度为O(alpha(n)n)。
某PbTfLcx大佬一直和我说路径压缩是O(n)的。然后在UOJ群里面搞了一发事情。然后就没有然后了。
不过似乎知道了，有一个啥二项树的东西可以把路径压缩卡到O(nlogn)。如果不是的话，那么实际复杂度是不是可以视为O(n)？
朴素的合并问题
这就是最表面的并查集。
BZOJ 1015
题目大意：
给出一张点数为n，边数为m的无向图，依次摧毁q个点。输出最初以及每一次摧毁之后连通块的个数。
n,m,q<=1e5
个人解法：
连通块的个数可以通过合并的时候统计。
既然这是删除，我们就离线操作时光倒流，变为合并即可统计。
复杂度为O(q+n+m)
（这tm是省选题嘛……）
BZOJ 3454
题目大意：
给出一张点数为n边数为m的无向图，边有边权。给出对于size=i的连通块的价值A[i]。求最短的区间[l..r]，使得保留边权为[l..r]的边之后，得到的图连通块的价值之和不小于给定的K。
n,m<=1e3
个人解法：
把边排序，枚举边被包含的左右端点，计算连通块的价值即可。
那么我们可以枚举左端点，右端点只往右边移动，每一次是合并，这样可以直接得到连通块的价值，更新答案即可。
复杂度为O(m^2)
BZOJ 3562
题目大意：
给出一张点数为n的图，给出q次操作：
加一条边
删一条边
查询连通块的个数
n,q<=1e3,m<=1e6
个人解法：
我们可以先把不用删除的边相连的点合并在一起。之后边数变为了O(q)级别。我们之后再暴力删边与加边即可。
时间复杂度O((n+q)q)
BZOJ 1104
题目大意：
给定一张n*m的海拔图，所有的点都被水淹没，现在有一些关键点，要求放最少的水泵使所有关键点的水都被抽干。水满足连通器原理。
n,m<=1e3
个人解法：
不难证明，水泵是可以全部在关键城市上的。
把所有格子按照高度排序。对于当前关键城市，比当前关键城市海拔低的点都被记录下来，并且相连的都被放在了一个集合中。
如果当前关键城市所在的集合中没有一个是水泵，就说明比之海拔低且可以到达其的点都没有水泵，那么就在这里建一个水泵。
相反，那么这个集合内所有的点放一个水泵都是可行的。那么就不用建水泵。
注意：一次要同时处理所有海拔相同的点。
用一个Done数组记录已经处理过的点，来保证当前点x不会和高度高于当前点x的点y合并。
时间复杂度O(nm)
处理删除问题
很奇怪玩意。并查集可以处理特殊一类问题——仅支持删除不支持合并的问题。当然这可能需要常用到离线操作时光倒流的技巧。
这个删除不是上文中合并的逆操作。上文中合并是信息的合并，但是这里的删除是集合内的元素的删除，而不是信息的分裂。这些事情用普通的容器维护也可以，比方说Treap或者set，但是都不如并查集来的速度与高效。
这样的并查集是O(nlogn)的，因为只能够路径压缩不能够按秩合并。但是常数比平衡树啥的小到不知道哪里去了。
由于大多数信息是支持合并的，所以在被分块莫队或者树套树等诸多数据结构洗脑之后，很少有人会想到并查集做这样的事情。
常运用在序列上。
BZOJ 3211/BZOJ 3038
题目大意：
给出一个长度为n的序列，给出m个操作：
区间每一个数字开根号
查询区间和
个人解法：
n,m<=1e5
发现一个数字开根号的次数不多，大概是log(logA[i])次。我们用树状数组维护区间和，暴力修改。
怎样减少枚举数量？我们可以尝试使用并查集，Fa[i]表示i或者i右边的第一个不是1或者0的数字。就知道需要修改哪一些数字了。
如果一个数字变为了1或者0，就令Fa[i]=Getfa(i+1)。在暴力修改的时候，直接跳到Getfa(i)。
时间复杂度O(mloglogA[i]+nlogn)
注意nlogn是路径压缩的复杂度。
BZOJ 3319
题目大意：
给出一棵大小为n的全0树（边权为0），给出m个操作：
路径边权赋值为1
查询一个节点到根的路径中第一条权值为1的边。
n,m<=1e6
个人解法：
首先自然边权转为点权。边的边权变为边连接的节点中深度较大的点的点权。
如果是查询节点到根的路径第一个权值为0的点，就很好操作。我们可以直接令Fa[i]为i到根的路径中第一个权值为0的点。由于路径赋值为1相当于删除权值为0的点，那么直接维护即可。
现在是查询第一个权值为1的点。我们尝试离线操作时光倒流，那么我们维护i到根路径上第一个权值为1的点。操作变为了路径赋值为0。
不过不能直接操作。我们需要记录一个点在什么时候变色。之后我们把变色的时间从大到小排序，就可以维护了。
至于记录第一次的变色时间，我们照样可以用并查集做同样的事情来维护。
时间复杂度O((n+m)logn)
BZOJ 1098
题目大意：
给出一张n个点m条边的无向图，将这张图分块，使得任意一对在不同块的点对都有边相连。
n,m<=1e5
个人解法：
问题可以转换为求反图的连通块的个数。
边有O(n^2)，自然不能用并查集来记录连通块。
我们可以采取DFS/BFS的方法寻找。
并查集不是维护连通块，而是Fa[i]记录下一个没有被找到的点。
时间复杂度O(nlogn)
BZOJ 4320
题目大意：
要求维护一个不可重集合，执行m次操作：
加入一个数字X。
查询集合内的数字modY的最大值。
X,Y<=3e5,m<=1e5
个人解法：
用平衡思想。分大于或者小于sqrt(3e5)来讨论。
对于大于sqrt(3e5)的问题，我们可以转换为枚举Y的倍数k，查询最小的不小于的k*Y的数字是多少。
同样建立一个并查集，我们令Fa[i]为不小于i的第一个数字即可。
由于只支持删除，我们继续离线操作时光倒流。
时间复杂度O(msqrt(Y)log(Y))。理论复杂度有这么高实际上飞快……
拆点问题
之前做的并查集一般就是拆点问题，例如“食物链”、“说谎岛”、CEOI99的“parity”、“家族”等等……这次似乎还是做到了一个（虽然这个题还不是用拆点做的）。
BZOJ 1370
题目大意：
给出n个人，给出m个关系，包括“F（朋友）”与“E（敌人）”。朋友是同一个帮派，敌人的敌人是朋友。现在最多有多少个帮派。
n,m<=1e5
个人解法：
对于a与b：
如果a与b是朋友关系，那么把a与b放入同一个集合。
如果a与b不是朋友关系，那么把a与b'放入同一个集合，把b与a'放入同一个集合。这样满足敌人的敌人是朋友
最后扫一遍即可知道有多少个集合，即帮派的个数。
（似乎就做了这一个）
带权并查集
这一部分就是很老的部分了。我们用Dist[x]表示x到其Fa[x]的权值。
支持路径压缩。一般也不写按秩合并。
BZOJ 3362
3362: [Usaco2004 Feb]Navigation Nightmare 导航噩梦
给出平面上n个点，给出m个关系，表示u在v的某一个方向x米。之后给出q个询问，查询两个点之间的曼哈顿距离。
如果不知道，输出-1。
n,m,q<=1e5。
个人解法：
我们就搞两个带权并查集就好了。
在查询的时候，如果两个点祖先不同，就可以输出-1。否则拿Dist加减拼凑一下即可。
横向的距离与纵向的距离是不干扰的。
注意在给出了一个“1在2的东边5米”，事实上也暗示了“1与2在南北方向相距0米”
时间复杂度O(mlogn+q)
BZOJ 1202
给出一个长度为n的区间，给出m条信息，每条信息表示[l..r]的区间和。判断这些区间和是否有矛盾。
n,m<=1e5。
个人解法：
一个带权并查集即可……
每一次判断是否合法，如果合法就加入到并查集里面，否则就可以标记“不合法”了。
时间复杂度O(mlogn)
连通块内边与点的关系处理与思维考察
一般需要找一个连通块里面的边与点的关系。
有些难想的感觉……
通常需要维护一个连通块里是否有环。
我们用tag[Getfa(x)]来记录x所在的连通块是否有环。只有一个并查集的根的tag才有意义。
我们在合并的时候可以实现对tag的更新。比方说在合并的时候如果fu==fv，那么tag[fu]|=1。
在路径压缩的时候也不必更新。一般情况下，如果维护的是其他的信息也是不用更新的。因为我们发现只有在初始化与合并的时候，信息可能会改变。当然还是具体情况具体分析。
可以按秩合并。
很多都是POI的题目。引用PoPoQQQ在WC2016的《论偏题的危害》一文的一段话吧——
BZOJ 1854
题目大意：
给出n个物品，每个物品有两个属性A[i]与B[i]。每个物品选择一种属性，使得[1..x]的权值都有。求最大的x。
n<=1e5，答案x<=1e4。
个人解法：
发现一个连通块如果是一棵树，那么这个连通块可以构成size-1个权值，如果有环（包括自环、重边）就可以构成size个权值
于是我们枚举x，直到“x在一棵树里面”+“x是连通块内最大点”，就输出x-1。
BZOJ 2079
给出一张n个点，m条边的无向图，每个点可以选择染上红色或者黑色，也可以不染。但是每个点以及相邻的点所构成的集合中必须要出现红色与黑色两个点。
n,m<=1e5。
个人解法：
自然连通块大小为1是不可能的。
连通块大小如果大于等于2，那么找到一种方案是不难的。考虑如果只有两种颜色，我们自然可以二分图染色，之后判断是否可行。现在可以选择不染，那么我们把矛盾的点不染就可以了。
问题变为找是否存在大小为1的连通块。并查集维护秩即可。
BZOJ 1116
题目大意：
给出一张n个点，m条边的无向图。要求使得其中一些边变为有向边，其他的边擦去，使得这张图每个点的入度为1.求是否存在方案。
n,m<=1e5
个人解法：
对于一个连通块而言：
一棵树自然不可能
如果在一棵树的基础上多了一条边，那么我们就把这个环的每一条边都变为首尾相接的有向边。之后不在环中的边变为“从环发散出去的有向边”即可。
如果多了更多的边，不选择即可。
于是问题变为了寻找一个连通块内是否有环。维护判断环的tag即可。
BZOJ 1529
给出一张n个点的有向图，每个点的出度为1。求环的个数。
n<=1e5
个人解法：
我似乎已经把题目转换出来了。
我们可以直接维护判断环的tag……不过我是做有向图，BFS+并查集。
类似于其NOIP2015的信息传递。
小结
有一种那一次复习Hash的感觉。
我且引用自己年轻的时候的一段话吧。
所以事实上Hash也是一种可以类似于线段树（树状数组）等树结构的数据结构，而不应该只是简简单单的一个Boolean数组。它同样还可以做到一些树结构难以做到的，例如指定方向的更新（如第一题中只能由前缀来更新）。
看来之前自己只会把Hash看成Boolean数组（还就这么对学弟说：Hash就是一个Boolean），简直有愧于于Hash表。
不过这些还只是Hash作为初等数据结构的简单应用（功能就还只是如树状数组对程序的优化一样，简单地查找可以用来更新的元素），每回想起很蒟蒻的时候，看的杨弋老师的论文，就会想，其实Hash肯定还有更高级的运用的吧。
哪个算法有何尝不是呢？
大概重新回顾这个数据结构的时候，有着全新的感受。
大概在之前的基础上，总结出这2天做的题目的几种类型。
大概开创并查集的大佬并没有在我们后人这么多的努力下，并查集已经有了如此之多的运用。
大概我这也是冰山一角吧。