简单并查集讲解
并查集
并查集是一种树型的数据结构，用于处理一些不相交集合的合并以及查询问题
其有两个基本操作：
- 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("%lld\n",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("%lld\n",ans);
}
}
}
}
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2019-12-26，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
