簡單並查集講解
- 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); } } } }
