This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub maspypy/library
#include "ds/unionfind/parallel_unionfind.hpp"
#include "mod/modint61.hpp" #include "random/base.hpp" struct Parallel_UnionFind { int n, log; using mint = modint61; vc<mint> seg; vc<mint> pow; mint base; vc<int> dat; vc<int> nxt; Parallel_UnionFind(int n) : n(n), dat(n, -1), nxt(n, -1) { log = 1; while ((1 << log) < n) ++log; base = RNG(mint::get_mod()); pow.resize(1 << log); pow[0] = 1; FOR(i, (1 << log) - 1) pow[i + 1] = pow[i] * base; seg.resize(2 << log); FOR(i, n) seg[i + (1 << log)] = i; FOR_R(i, 1, (1 << log)) update(i); } int operator[](int x) { return (dat[x] < 0 ? x : dat[x]); } int size(int x) { assert(dat[x] < 0); return -dat[x]; } // unite [a,b) [c,d). // f(v, y, x): root(v) = y -> root(v) = x template <typename F> void merge( int a, int b, int c, int d, F f = [](int v, int y, int x) -> void {}) { assert(0 <= a && a <= b && b <= n); assert(0 <= c && c <= d && d <= n); assert(b - a == d - c); while (1) { if (get(a, b) == get(c, d)) break; int n = binary_search( [&](int k) -> bool { return get(a, a + k) == get(c, c + k); }, 0, b - a, false); int x = (*this)[a + n], y = (*this)[c + n]; a += n, c += n; if (size(x) < size(y)) swap(x, y); // 成分 y を成分 x にマージ while (nxt[y] != -1) { int v = nxt[y]; nxt[y] = nxt[v]; set(v, x), f(v, y, x); dat[v] = x, dat[x] -= 1, nxt[v] = nxt[x], nxt[x] = v; } set(y, x), f(y, y, x); dat[y] = x, dat[x] -= 1, nxt[y] = nxt[x], nxt[x] = y; } } template <typename F> void merge( int a, int b, F f = [](int v, int y, int x) -> void {}) { merge(a, a + 1, b, b + 1, f); } private: void update(int i) { int sz = 1 << (log - topbit(i) - 1); seg[i] = seg[2 * i] * pow[sz] + seg[2 * i + 1]; } void set(int i, mint x) { assert(i < n); seg[i += (1 << log)] = x; while (i >>= 1) update(i); } mint get(int L, int R) { assert(0 <= L && L <= R && R <= n); mint xl = 0, xr = 0; int sl = 0, sr = 0; L += (1 << log), R += (1 << log); int s = 1; while (L < R) { if (L & 1) { xl = xl * pow[s] + seg[L++], sl += s; } if (R & 1) { xr = seg[--R] * pow[sr] + xr, sr += s; } L >>= 1, R >>= 1, s <<= 1; } return xl * pow[sr] + xr; } };
#line 2 "mod/modint61.hpp" struct modint61 { static constexpr u64 mod = (1ULL << 61) - 1; u64 val; constexpr modint61() : val(0ULL) {} constexpr modint61(u32 x) : val(x) {} constexpr modint61(u64 x) : val(x % mod) {} constexpr modint61(int x) : val((x < 0) ? (x + static_cast<ll>(mod)) : x) {} constexpr modint61(ll x) : val(((x %= static_cast<ll>(mod)) < 0) ? (x + static_cast<ll>(mod)) : x) {} static constexpr u64 get_mod() { return mod; } modint61 &operator+=(const modint61 &a) { val = ((val += a.val) >= mod) ? (val - mod) : val; return *this; } modint61 &operator-=(const modint61 &a) { val = ((val -= a.val) >= mod) ? (val + mod) : val; return *this; } modint61 &operator*=(const modint61 &a) { const unsigned __int128 y = static_cast<unsigned __int128>(val) * a.val; val = (y >> 61) + (y & mod); val = (val >= mod) ? (val - mod) : val; return *this; } modint61 operator-() const { return modint61(val ? mod - val : u64(0)); } modint61 &operator/=(const modint61 &a) { return (*this *= a.inverse()); } modint61 operator+(const modint61 &p) const { return modint61(*this) += p; } modint61 operator-(const modint61 &p) const { return modint61(*this) -= p; } modint61 operator*(const modint61 &p) const { return modint61(*this) *= p; } modint61 operator/(const modint61 &p) const { return modint61(*this) /= p; } bool operator==(const modint61 &p) const { return val == p.val; } bool operator!=(const modint61 &p) const { return val != p.val; } modint61 inverse() const { ll a = val, b = mod, u = 1, v = 0, t; while (b > 0) { t = a / b; swap(a -= t * b, b), swap(u -= t * v, v); } return modint61(u); } modint61 pow(ll n) const { assert(n >= 0); modint61 ret(1), mul(val); while (n > 0) { if (n & 1) ret *= mul; mul *= mul, n >>= 1; } return ret; } }; #ifdef FASTIO void rd(modint61 &x) { fastio::rd(x.val); assert(0 <= x.val && x.val < modint61::mod); } void wt(modint61 x) { fastio::wt(x.val); } #endif #line 2 "random/base.hpp" u64 RNG_64() { static uint64_t x_ = uint64_t(chrono::duration_cast<chrono::nanoseconds>( chrono::high_resolution_clock::now().time_since_epoch()) .count()) * 10150724397891781847ULL; x_ ^= x_ << 7; return x_ ^= x_ >> 9; } u64 RNG(u64 lim) { return RNG_64() % lim; } ll RNG(ll l, ll r) { return l + RNG_64() % (r - l); } #line 3 "ds/unionfind/parallel_unionfind.hpp" struct Parallel_UnionFind { int n, log; using mint = modint61; vc<mint> seg; vc<mint> pow; mint base; vc<int> dat; vc<int> nxt; Parallel_UnionFind(int n) : n(n), dat(n, -1), nxt(n, -1) { log = 1; while ((1 << log) < n) ++log; base = RNG(mint::get_mod()); pow.resize(1 << log); pow[0] = 1; FOR(i, (1 << log) - 1) pow[i + 1] = pow[i] * base; seg.resize(2 << log); FOR(i, n) seg[i + (1 << log)] = i; FOR_R(i, 1, (1 << log)) update(i); } int operator[](int x) { return (dat[x] < 0 ? x : dat[x]); } int size(int x) { assert(dat[x] < 0); return -dat[x]; } // unite [a,b) [c,d). // f(v, y, x): root(v) = y -> root(v) = x template <typename F> void merge( int a, int b, int c, int d, F f = [](int v, int y, int x) -> void {}) { assert(0 <= a && a <= b && b <= n); assert(0 <= c && c <= d && d <= n); assert(b - a == d - c); while (1) { if (get(a, b) == get(c, d)) break; int n = binary_search( [&](int k) -> bool { return get(a, a + k) == get(c, c + k); }, 0, b - a, false); int x = (*this)[a + n], y = (*this)[c + n]; a += n, c += n; if (size(x) < size(y)) swap(x, y); // 成分 y を成分 x にマージ while (nxt[y] != -1) { int v = nxt[y]; nxt[y] = nxt[v]; set(v, x), f(v, y, x); dat[v] = x, dat[x] -= 1, nxt[v] = nxt[x], nxt[x] = v; } set(y, x), f(y, y, x); dat[y] = x, dat[x] -= 1, nxt[y] = nxt[x], nxt[x] = y; } } template <typename F> void merge( int a, int b, F f = [](int v, int y, int x) -> void {}) { merge(a, a + 1, b, b + 1, f); } private: void update(int i) { int sz = 1 << (log - topbit(i) - 1); seg[i] = seg[2 * i] * pow[sz] + seg[2 * i + 1]; } void set(int i, mint x) { assert(i < n); seg[i += (1 << log)] = x; while (i >>= 1) update(i); } mint get(int L, int R) { assert(0 <= L && L <= R && R <= n); mint xl = 0, xr = 0; int sl = 0, sr = 0; L += (1 << log), R += (1 << log); int s = 1; while (L < R) { if (L & 1) { xl = xl * pow[s] + seg[L++], sl += s; } if (R & 1) { xr = seg[--R] * pow[sr] + xr, sr += s; } L >>= 1, R >>= 1, s <<= 1; } return xl * pow[sr] + xr; } };