- 部分永続Union Findとも言うらしい
- 各uniteしたときに時刻が1進むとして、各時刻での連結情報が取れる、記憶力の良いUF
struct PersistentUnionFind{
VI parent;
VI time;
VI rank;
ll now;
vector<vector<PII>> num;
PersistentUnionFind(ll sz){
parent.resize(sz);
rep(i,sz) parent[i]=i;
now = 0;
time.resize(sz, inf);
rank.resize(sz, 0);
num.resize(sz);
rep(i,sz) num[i].push_back(MP(0,1));
debug("initialize finished");
}
void unite(ll a, ll b){
now++;
ll rootA = findRoot(a, now);
ll rootB = findRoot(b, now);
if(rootA==rootB) return;
if(rank[rootA]<rank[rootB]) swap(rootA, rootB);
ll merged_size = size(rootA, now) + size(rootB, now);
num[rootA].push_back(MP(now, merged_size));
parent[rootB] = rootA;
time[rootB] = now;
if(rank[rootA]==rank[rootB]){
rank[rootA]++;
}
debug("unite", a, b, "finished");
}
ll findRoot(ll a, ll t){
if(time[a]>t){
return a;
}
else{
return findRoot(parent[a], t);
}
}
bool is_same(ll u, ll v, ll t){
return findRoot(u,t) == findRoot(v,t);
}
ll size(ll u, ll t){
ll r = findRoot(u, t);
ll left = 0;
ll right = num[r].size();
while(left+1!=right){
ll center = (left+right)/2;
if(num[r][center].first>t){
right = center;
}else{
left = center;
}
}
return num[r][left].second;
}
};
verified
- D - Stamp Rally
- O - 可変全域木