sotanishy's code snippets for competitive programming
#include "data-structure/unionfind/partially_persistent_union_find.hpp"
部分永続 union find は素集合森の過去の連結性に関する情報を保持する.以下の操作を提供する:
空間計算量: $O(n + q)$
PartiallyPersistentUnionFind(int n)
n
の部分永続 union find を構築する.時刻の初期値は 0 である.int find(int t, int x)
void unite(int x, int y)
bool same(int t, int x, int y)
int size(int t, int x)
#pragma once
#include <algorithm>
#include <limits>
#include <utility>
#include <vector>
class PartiallyPersistentUnionFind {
public:
PartiallyPersistentUnionFind() = default;
explicit PartiallyPersistentUnionFind(int n)
: data(n, -1), time(n, INF), sz(n, {{0, 1}}) {}
int find(int t, int x) const {
if (t < time[x]) return x;
return find(t, data[x]);
}
void unite(int x, int y) {
++now;
x = find(now, x);
y = find(now, y);
if (x == y) return;
if (data[x] > data[y]) std::swap(x, y);
data[x] += data[y];
sz[x].emplace_back(now, -data[x]);
data[y] = x;
time[y] = now;
}
bool same(int t, int x, int y) const { return find(t, x) == find(t, y); }
int size(int t, int x) const {
x = find(t, x);
return (--std::ranges::lower_bound(sz[x], std::make_pair(t, INF)))
->second;
}
private:
static constexpr int INF = std::numeric_limits<int>::max();
std::vector<int> data;
std::vector<int> time;
std::vector<std::vector<std::pair<int, int>>> sz;
int now = 0;
};
#line 2 "data-structure/unionfind/partially_persistent_union_find.hpp"
#include <algorithm>
#include <limits>
#include <utility>
#include <vector>
class PartiallyPersistentUnionFind {
public:
PartiallyPersistentUnionFind() = default;
explicit PartiallyPersistentUnionFind(int n)
: data(n, -1), time(n, INF), sz(n, {{0, 1}}) {}
int find(int t, int x) const {
if (t < time[x]) return x;
return find(t, data[x]);
}
void unite(int x, int y) {
++now;
x = find(now, x);
y = find(now, y);
if (x == y) return;
if (data[x] > data[y]) std::swap(x, y);
data[x] += data[y];
sz[x].emplace_back(now, -data[x]);
data[y] = x;
time[y] = now;
}
bool same(int t, int x, int y) const { return find(t, x) == find(t, y); }
int size(int t, int x) const {
x = find(t, x);
return (--std::ranges::lower_bound(sz[x], std::make_pair(t, INF)))
->second;
}
private:
static constexpr int INF = std::numeric_limits<int>::max();
std::vector<int> data;
std::vector<int> time;
std::vector<std::vector<std::pair<int, int>>> sz;
int now = 0;
};