Static Range Union Find
(data-structure/unionfind/static_range_union_find.hpp)

View this file on GitHub
Last update: 2024-05-07 01:21:06+09:00
Include: #include "data-structure/unionfind/static_range_union_find.hpp"

Description

区間に対するマージクエリを静的に処理する．

空間計算量: $O(n\alpha(n) + q)$

Operations

StaticRangeUnionFind(int n)
- サイズnの union find を構築する．
- 時間計算量: $O(n)$
void unite(int x, int y, int len)
- $[x, x+\mathrm{len})$ と $[y,y+\mathrm{len})$ が属する集合を連結する
- 時間計算量: $O(1)$
vector<int> run()
- 各頂点が属する集合の代表元を返す
- 時間計算量: $O(n\alpha(n) + q)$, $q$ は unite クエリの個数

Note

アルゴリズムを説明する．このアルゴリズムは yosupo 氏による（参考文献参照）．

unite クエリを $\mathrm{len}$ の降順に処理する．クエリ $(x,y,\mathrm{len})$ に対する処理は以下のようにする．

$x,y$ が同じ集合に属していれば，このクエリの処理を終了する
$x,y$ が属する集合をマージし，新たにクエリ $(x+1,y+1,\mathrm{len}-1)$ を追加する

マージが起こる回数はたかだか $n-1$ 回である．また， $(x,y,\mathrm{len})$ の処理を行う際に， $x,y$ がすでに同じ集合に属しているならば，より $\mathrm{len}$ が大きいようなクエリで $(x+1,y+1),(x+2,y+2),\dots$ もすでに処理されているはずだから，このアルゴリズムは正しく動作する．

Reference

Depends on

Union Find (data-structure/unionfind/union_find.hpp)

Code

#pragma once
#include <cassert>
#include <utility>
#include <vector>

#include "union_find.hpp"

class StaticRangeUnionFind {
   public:
    StaticRangeUnionFind() = default;
    explicit StaticRangeUnionFind(int n) : n(n), uf(n), lst(n) {}

    void unite(int x, int y, int len) {
        assert(x + len <= n && y + len <= n);
        if (x == y) return;
        lst[len].push_back({x, y});
    }

    std::vector<int> run() {
        for (int len = n - 1; len >= 1; --len) {
            for (auto [x, y] : lst[len]) {
                if (uf.same(x, y)) continue;
                uf.unite(x, y);
                if (len > 1) lst[len - 1].push_back({x + 1, y + 1});
            }
        }
        std::vector<int> res(n);
        for (int i = 0; i < n; ++i) res[i] = uf.find(i);
        return res;
    }

   private:
    int n;
    UnionFind uf;
    std::vector<std::vector<std::pair<int, int>>> lst;
};

#line 2 "data-structure/unionfind/static_range_union_find.hpp"
#include <cassert>
#include <utility>
#include <vector>

#line 2 "data-structure/unionfind/union_find.hpp"
#include <algorithm>
#line 4 "data-structure/unionfind/union_find.hpp"

class UnionFind {
   public:
    UnionFind() = default;
    explicit UnionFind(int n) : data(n, -1) {}

    int find(int x) {
        if (data[x] < 0) return x;
        return data[x] = find(data[x]);
    }

    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return;
        if (data[x] > data[y]) std::swap(x, y);
        data[x] += data[y];
        data[y] = x;
    }

    bool same(int x, int y) { return find(x) == find(y); }

    int size(int x) { return -data[find(x)]; }

   private:
    std::vector<int> data;
};
#line 7 "data-structure/unionfind/static_range_union_find.hpp"

class StaticRangeUnionFind {
   public:
    StaticRangeUnionFind() = default;
    explicit StaticRangeUnionFind(int n) : n(n), uf(n), lst(n) {}

    void unite(int x, int y, int len) {
        assert(x + len <= n && y + len <= n);
        if (x == y) return;
        lst[len].push_back({x, y});
    }

    std::vector<int> run() {
        for (int len = n - 1; len >= 1; --len) {
            for (auto [x, y] : lst[len]) {
                if (uf.same(x, y)) continue;
                uf.unite(x, y);
                if (len > 1) lst[len - 1].push_back({x + 1, y + 1});
            }
        }
        std::vector<int> res(n);
        for (int i = 0; i < n; ++i) res[i] = uf.find(i);
        return res;
    }

   private:
    int n;
    UnionFind uf;
    std::vector<std::vector<std::pair<int, int>>> lst;
};

Static Range Union Find (data-structure/unionfind/static_range_union_find.hpp)