简单并查集讲解
- 2020 年 1 月 2 日
- 筆記
并查集
并查集是一种树型的数据结构，用于处理一些不相交集合的合并以及查询问题
其有两个基本操作：
- 1.合并两个不相交的集合。
- 2.判断两个元素是否属于同一个集合
关于其算法流程：
- 1.初始化 在一个数组中进行，首先令每个元素的父结点是其本身，即：
- 2.合并 合并，两个集合，先找到，的根结点，将一个集合的根结点指向另外一个集合的根结点
- 3.查询 可转化为判断两个元素的根结点是否相同，直接递归查询即可
但是这里存在一个很显然的问题。对于一条链来说，我们查询叶子结点的祖先的时候会把所有结点都遍历一遍，为了避免这种情况，我们可以有两种策略对其优化
- 1.路径压缩 在回溯的时候将其子孙结点都指向其祖先，这样再次查询时就会变成的复杂度。
- 2.按秩合并 元素秩小的集合合并到元素秩大的集合中，对于秩的定义由实际情况来决定可以是树的大小也可以是树的高度 //路径压缩 int find(int x) { return p[x] == x ? p[x] : p[x] = find(p[x]); } //按秩合并 void merge(int x, int y) { int rx = finx(x), ry = find(y); if(rx != ry) { if(rank[rx] <= rank[ry]) { p[rx] = ry; if(rank[rx] == rank[ry]) { rank[ry]++; } } else { p[ry] = rx; } } } 可以看到路径压缩是非常随意的直接连向祖先，而按秩合并相对有一定的约束，所以当在处理一些和权值有关的问题的时候随意的压缩路径，会使得信息没有办法维护。
问题主要出现在
- 1.每个结点在压缩之前记录的是和父结点之间的权值，在find之后该点与根结点直接相连，权值应当做相应的更新。
- 2.在两个并查集做合并的时候，权值也应该更新，一个根结点必定会成为另外一个根结点的子结点，这个权值也需要更新。
这样我们需要这两个问题有两套修改方案
- 1.路径压缩时,因为父亲变了，原来3到1需要到2再到1，显然现在直接到1的话权值会变成原来的路上权值和。
- 2.合并时更新权值，假设到的权值为，在处理时发现不在同一个集合，这个时候我需要把所在的集合的根结点合并。很显然合并之后我们经过到达和经过到达的权值应该相同，设我们从的权值是。所以有 即：
这些大家都懂，下面看两道题道题。
给个正整数, 有次操作，每次操作删去一个数，直到每个数都被删掉，对于每次操作，求出最大的连续段的和。
input
4 1 3 2 5 3 4 1 2
output
5 4 3 0
样例解释
一开始有四个数 。
第一个操作之后被删除，剩下两个连续子段和。前一个连续子段和为4，后一个为5，输出最大所以第一个操作之后的答案为5
第二个操作之后被删除，剩，答案为4
第三个操作之后被删除。剩，答案为3
最后全被删除答案为0。
题解
我们可以把这个删除操作，考虑成增加的操作相当于从一个空序列往上添加值，加一次，求一次线段的最大和，把操作都记下来，每次与当前值和前一个答案来更新答案。
在每次在处加入新的值的时候，判断与，的位置是否已经存在，若存在，则用并查集合并，把贡献全部累加到根节点上即可。
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 4e5+5; #define INF 0x3f3f3f3f ll p[maxn]; ll find(ll x){ return p[x] == x ? x : p[x] = find(p[x]); } ll a[maxn],b[maxn]; bool flag[maxn]; ll sum[maxn], ans[maxn]; int main(){ int n = 0; scanf("%d", &n); for(int i = 1;i <= n;i++){ p[i] = i; } for(int i = 1;i <= n;i++){ scanf("%d", a + i); } for(int i = 1;i <= n;i++){ scanf("%d", b + i); } for(int i = n;i >= 1;i--){ ll pos = b[i]; sum[pos] = a[pos]; flag[pos] = 1; if(flag[pos - 1]){ int rx = find(pos), ry = find(pos-1); p[rx] = ry; sum[ry] += sum[rx]; } if(flag[pos + 1]){ int rx = find(pos), ry = find(pos + 1); p[rx] = ry; sum[ry] += sum[rx]; } ans[i-1] = max(ans[i],sum[find(pos)]); } for(int i = 1;i <= n;i++){ printf("%lldn",ans[i]); } return 0; }
C1664 2018 Wannafly winter camp day3 I
input
3 5 2 1 1 2 1 2 1 1 2 3 2 1
output
27 9 6
题解
直接来分析这个猜拳的过程，挑战者去找被挑战者猜拳，留在他自己位置上的概率是（赢和平），占的位置的概率是，对于有这么一次操作，场上就会发生一次这样的变动。考虑以下几点：
- 1.在没有任何1操作之前，无论怎么发牌每个人都可以留在场上，所以不管查询谁，答案都是
- 2.每进行一次1操作，挑战者为了留下来，牌的种类数只能变成，被挑战者为了留下来变成
- 3.所以对于每个选手，挑战别人的次数为，被别人挑战的次数为，最后对于该选手的查询答案就是，统计即可。
- 4.我们可以保留下所有1操作，在有2操作时遍历一遍前面所有1操作，但这显然会超时。但我们又不能直接开数组将，记下来，因为题目是撤去一个人的座位，并不是直接赶走某一个人，这个座位上坐的是几号人不清楚，只是存在一个可能性。
- 5.所以不妨将每个座位看成一个集合，集合内存可能坐在该位置上的选手的编号，对于1操作，相当合并两个集合，在将，作为权记录下来，用带权并查集来维护即可。(注意本题中根节点本身也有权)。
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MOD = 998244353; #define mod(x) x % MOD const int maxn = 4e5+5; ll qpow(ll a,int b){ ll res = 1; a = mod(a); while(b){ if(b & 1) res = mod(res * a); a = mod(a * a); b >>= 1; } return mod(res); } int p[maxn], n, m; ll a[maxn],b[maxn]; int find(int x){ if(x == p[x]){ return x; } else{ int t = p[x]; p[x] = find(p[x]); if(t!=p[x]){ a[x] += a[t], b[x] += b[t]; } return p[x]; } } int main(){ while(~scanf("%d %d",&n,&m)){ memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); for(int i = 1;i <= n;i++){ p[i] = i; } int x = 0,y = 0; for(int i = 1; i <= m;i++){ int kind = 0; scanf("%d",&kind); if(kind == 1){ scanf("%d %d",&x,&y); a[x]++,b[y]++; p[y] = x; a[y] -= a[x], b[y] -= b[x]; } else if(kind == 2){ scanf("%d",&x); int rt = find(x), res = qpow(3,n); ll inv1 = 1ll*qpow(3,MOD-2), inv2 = mod(2 * 1ll * inv1); ll resa = mod(qpow(inv2,a[rt])), resb = qpow(inv1,b[rt]), ans = 0; if(rt == x){ ans = mod(mod(mod(1ll * res * resa) * resb)); } else{ resa = mod(qpow(inv2, (a[rt] + a[x]))); resb = mod(qpow(inv1, b[rt] + b[x])); ans = mod(mod(mod(1ll * res * resa) * resb)); } printf("%lldn",ans); } } } }
