This documentation is automatically generated by online-judge-tools/verification-helper
#include "data_structure/partially_persistent_unionfind.hpp"
時刻 $t$ での $v$ の親を返す。 $O(\log N)$
$a$ と $b$ のグループをマージする。 $O(\log N)$
時刻 $t$ で $a$ と $b$ が同じグループに属するか判定する。 $O(\log N)$
#pragma once
#include <algorithm>
#include <limits>
#include <vector>
/*
refernce: https://noshi91.hatenablog.com/entry/2018/02/18/161529
verify:
https://atcoder.jp/contests/code-thanks-festival-2017-open/submissions/21131946
*/
namespace ebi {
struct partially_persistent_unionfind {
private:
int now = 0;
std::vector<int> par, time;
std::vector<std::vector<std::pair<int, int>>> data;
public:
partially_persistent_unionfind(int n)
: par(n, 1), time(n, std::numeric_limits<int>::max()), data(n) {
for (auto &v : data) {
v.emplace_back(0, 1);
}
}
int find(int t, int v) {
if (time[v] > t)
return v;
else
return find(t, par[v]);
}
bool merge(int a, int b) {
++now;
a = find(now, a);
b = find(now, b);
if (a == b) return false;
if (par[a] < par[b]) std::swap(a, b);
par[a] += par[b];
data[a].emplace_back(now, par[a]);
par[b] = a;
time[b] = now;
return true;
}
bool same(int t, int a, int b) {
return find(t, a) == find(t, b);
}
int size(int t, int v) {
v = find(t, v);
return std::prev(
std::upper_bound(
data[v].begin(), data[v].end(),
std::pair<int, int>(t, std::numeric_limits<int>::max())))
->second;
}
};
} // namespace ebi
#line 2 "data_structure/partially_persistent_unionfind.hpp"
#include <algorithm>
#include <limits>
#include <vector>
/*
refernce: https://noshi91.hatenablog.com/entry/2018/02/18/161529
verify:
https://atcoder.jp/contests/code-thanks-festival-2017-open/submissions/21131946
*/
namespace ebi {
struct partially_persistent_unionfind {
private:
int now = 0;
std::vector<int> par, time;
std::vector<std::vector<std::pair<int, int>>> data;
public:
partially_persistent_unionfind(int n)
: par(n, 1), time(n, std::numeric_limits<int>::max()), data(n) {
for (auto &v : data) {
v.emplace_back(0, 1);
}
}
int find(int t, int v) {
if (time[v] > t)
return v;
else
return find(t, par[v]);
}
bool merge(int a, int b) {
++now;
a = find(now, a);
b = find(now, b);
if (a == b) return false;
if (par[a] < par[b]) std::swap(a, b);
par[a] += par[b];
data[a].emplace_back(now, par[a]);
par[b] = a;
time[b] = now;
return true;
}
bool same(int t, int a, int b) {
return find(t, a) == find(t, b);
}
int size(int t, int v) {
v = find(t, v);
return std::prev(
std::upper_bound(
data[v].begin(), data[v].end(),
std::pair<int, int>(t, std::numeric_limits<int>::max())))
->second;
}
};
} // namespace ebi