data_structure/offline_dynamic_connectivity.hpp

• View this file on GitHub
• Last update: 2024-09-20 17:32:12+09:00
• Include: #include "data_structure/offline_dynamic_connectivity.hpp"

Depends on

• data_structure/rollback_dsu.hpp

Verified with

• test/data_structure/aoj_2235.test.cpp

Code

#pragma once

#include"../data_structure/rollback_dsu.hpp"

#include <vector>
#include <utility>
#include <cassert>

namespace noya2 {

struct offline_dynamic_connectivity : rollback_dsu {
    using rollback_dsu::operator=;
    offline_dynamic_connectivity () {}
    offline_dynamic_connectivity (int _n, unsigned int t_max, size_t reserve_edge = 0) : n(_n) {
        sz = bit_ceil(t_max);
        ids.resize(sz*2);
        *this = rollback_dsu(n);
        edges.reserve(reserve_edge);
        inner_clock = -1;
    }
    // for time interval [l, r), connect u, v
    void add_edge(int l, int r, int u, int v){
        assert(0 <= l && l <= r && r <= sz);
        assert(0 <= u && u < n && 0 <= v && v < n);
        l += sz, r += sz;
        int edge_id = edges.size();
        while (l < r){
            if (l & 1) ids[l++].push_back(edge_id);
            if (r & 1) ids[--r].push_back(edge_id);
            l >>= 1, r >>= 1;
        }
        edges.emplace_back(u,v);
    }
    void build(){
        inner_clock = 1;
        while (true){
            add_block(inner_clock);
            if (inner_clock == sz) break;
            inner_clock <<= 1;
        }
    }
    // leap to time t, change this dsu
    void set(int t){
        assert(0 <= t && t < sz && inner_clock != -1);
        t += sz;
        if (inner_clock == t) return ;
        int k = 32 - countl_zero((unsigned int)(inner_clock ^ t));
        for (int i = 0; i < k; i++){
            del_block(inner_clock);
            inner_clock >>= 1;
        }
        for (int i = k-1; i >= 0; i--){
            inner_clock <<= 1;
            if (t >> i & 1) inner_clock++;
            add_block(inner_clock);
        }
        inner_clock = t;
    }
  private:
    void add_block(int i){
        for (auto &id : ids[i]){
            this->merge(edges[id].first,edges[id].second);
        }
    }
    void del_block(int i){
        int ctr = ids[i].size();
        while (ctr--) this->rollback();
    }
    int n, sz, inner_clock;
    std::vector<std::vector<int>> ids;
    std::vector<std::pair<int,int>> edges;
};

} // namespace noya2

#line 2 "data_structure/offline_dynamic_connectivity.hpp"

#line 2 "data_structure/rollback_dsu.hpp"

#include <vector>
#include <stack>
#include <utility>
#include <cassert>

namespace noya2 {

struct rollback_dsu {
    rollback_dsu (int _n = 0) : n(_n), par_or_siz(_n,-1) {}
    int leader(int v){
        assert(0 <= v && v < n);
        if (par_or_siz[v] < 0) return v;
        return leader(par_or_siz[v]);
    }
    bool same(int u, int v){
        return leader(u) == leader(v);
    }
    int merge(int u, int v){
        u = leader(u);
        v = leader(v);
        logs.push(make_pair(u,par_or_siz[u]));
        logs.push(make_pair(v,par_or_siz[v]));
        if (u == v) return u;
        if (-par_or_siz[u] < -par_or_siz[v]) std::swap(u,v);
        par_or_siz[u] += par_or_siz[v];
        par_or_siz[v] = u;
        return u;
    }
    int size(int v){
        return -par_or_siz[leader(v)];
    }
    void rollback(){
        par_or_siz[logs.top().first] = logs.top().second; logs.pop();
        par_or_siz[logs.top().first] = logs.top().second; logs.pop();
    }
  private:
    int n;
    std::vector<int> par_or_siz;
    std::stack<std::pair<int,int>> logs;
};

} // namespace noya2
#line 4 "data_structure/offline_dynamic_connectivity.hpp"

#line 8 "data_structure/offline_dynamic_connectivity.hpp"

namespace noya2 {

struct offline_dynamic_connectivity : rollback_dsu {
    using rollback_dsu::operator=;
    offline_dynamic_connectivity () {}
    offline_dynamic_connectivity (int _n, unsigned int t_max, size_t reserve_edge = 0) : n(_n) {
        sz = bit_ceil(t_max);
        ids.resize(sz*2);
        *this = rollback_dsu(n);
        edges.reserve(reserve_edge);
        inner_clock = -1;
    }
    // for time interval [l, r), connect u, v
    void add_edge(int l, int r, int u, int v){
        assert(0 <= l && l <= r && r <= sz);
        assert(0 <= u && u < n && 0 <= v && v < n);
        l += sz, r += sz;
        int edge_id = edges.size();
        while (l < r){
            if (l & 1) ids[l++].push_back(edge_id);
            if (r & 1) ids[--r].push_back(edge_id);
            l >>= 1, r >>= 1;
        }
        edges.emplace_back(u,v);
    }
    void build(){
        inner_clock = 1;
        while (true){
            add_block(inner_clock);
            if (inner_clock == sz) break;
            inner_clock <<= 1;
        }
    }
    // leap to time t, change this dsu
    void set(int t){
        assert(0 <= t && t < sz && inner_clock != -1);
        t += sz;
        if (inner_clock == t) return ;
        int k = 32 - countl_zero((unsigned int)(inner_clock ^ t));
        for (int i = 0; i < k; i++){
            del_block(inner_clock);
            inner_clock >>= 1;
        }
        for (int i = k-1; i >= 0; i--){
            inner_clock <<= 1;
            if (t >> i & 1) inner_clock++;
            add_block(inner_clock);
        }
        inner_clock = t;
    }
  private:
    void add_block(int i){
        for (auto &id : ids[i]){
            this->merge(edges[id].first,edges[id].second);
        }
    }
    void del_block(int i){
        int ctr = ids[i].size();
        while (ctr--) this->rollback();
    }
    int n, sz, inner_clock;
    std::vector<std::vector<int>> ids;
    std::vector<std::pair<int,int>> edges;
};

} // namespace noya2

Back to top page