library

This documentation is automatically generated by online-judge-tools/verification-helper

---

Project maintained by tko919 Hosted on GitHub Pages — Theme by mattgraham

Range Parallel UnionFind
(DataStructure/rangeparalleluf.hpp)

• View this file on GitHub
• Last update: 2024-06-14 02:46:58+09:00
• Include: #include "DataStructure/rangeparalleluf.hpp"

Depends on

• Union Find (DataStructure/unionfind.hpp)

Code

#pragma once
#include "DataStructure/unionfind.hpp"

struct RangeParallelUF {
    vector<UnionFind> buf;
    RangeParallelUF(int n) {
        int lg = topbit(n) + 2;
        buf.resize(lg);
        rep(i, 0, lg) buf[i] = UnionFind(n);
    }
    template <typename F> void unite(int x, int y, int len, F f) {
        if (len == 0)
            return;
        if (len == 1) {
            inner(x, y, 0, f);
            return;
        }
        int k = topbit(len - 1);
        inner(x, y, k, f);
        inner(x + len - (1 << k), y + len - (1 << k), k, f);
    }

  private:
    template <typename F> void inner(int x, int y, int k, F f) {
        if (k == 0) {
            int a = buf[0].root(x);
            int b = buf[0].root(y);
            if (a == b)
                return;
            buf[0].unite(a, b);
            int c = buf[0].root(x);
            f(c, a ^ b ^ c);
            return;
        }
        if (!buf[k].unite(x, y))
            return;
        inner(x, y, k - 1, f);
        inner(x + (1 << (k - 1)), y + (1 << (k - 1)), k - 1, f);
    }
};

/**
 * @brief Range Parallel UnionFind
 */

#line 2 "DataStructure/unionfind.hpp"

struct UnionFind{
    vector<int> par; int n;
    UnionFind(){}
    UnionFind(int _n):par(_n,-1),n(_n){}
    int root(int x){return par[x]<0?x:par[x]=root(par[x]);}
    bool same(int x,int y){return root(x)==root(y);}
    int size(int x){return -par[root(x)];}
    bool unite(int x,int y){
        x=root(x),y=root(y); if(x==y)return false;
        if(size(x)>size(y))swap(x,y);
        par[y]+=par[x]; par[x]=y; n--; return true;
    }
};

/**
 * @brief Union Find
 */
#line 3 "DataStructure/rangeparalleluf.hpp"

struct RangeParallelUF {
    vector<UnionFind> buf;
    RangeParallelUF(int n) {
        int lg = topbit(n) + 2;
        buf.resize(lg);
        rep(i, 0, lg) buf[i] = UnionFind(n);
    }
    template <typename F> void unite(int x, int y, int len, F f) {
        if (len == 0)
            return;
        if (len == 1) {
            inner(x, y, 0, f);
            return;
        }
        int k = topbit(len - 1);
        inner(x, y, k, f);
        inner(x + len - (1 << k), y + len - (1 << k), k, f);
    }

  private:
    template <typename F> void inner(int x, int y, int k, F f) {
        if (k == 0) {
            int a = buf[0].root(x);
            int b = buf[0].root(y);
            if (a == b)
                return;
            buf[0].unite(a, b);
            int c = buf[0].root(x);
            f(c, a ^ b ^ c);
            return;
        }
        if (!buf[k].unite(x, y))
            return;
        inner(x, y, k - 1, f);
        inner(x + (1 << (k - 1)), y + (1 << (k - 1)), k - 1, f);
    }
};

/**
 * @brief Range Parallel UnionFind
 */

Back to top page