competitive-programing

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

View the Project on GitHub Astral-23/competitive-programing

:heavy_check_mark: offline_connectivity
(Datastructure/offline_connectivity.hpp)

概要

クエリが先読み可能な時のグラフのconnectivity。logが2つつくが、比較的高速である。 参考 : https://ei1333.github.io/luzhiled/snippets/other/offline-dynamic-connectivity.html

コンストラクタ

offline_connectivity<dsu, S, qif, (bool)multi_edge> uf(n) … [0, n) の頂点のグラフを作成する。 計算量$O(n)$

無効の時
link(u, v) : u - v辺が既にあるならば、何もしない。無かったら、u-v辺を追加する。
cut(u, v) :u - v辺が存在するならば切る。存在しなければ何もしない。

有効の時
link(u, v) : u - v辺を1本追加する。
cut(u, v) : u - v辺が存在するのなら1本切る。

関数

using dsu = undable_dsu;
using S = int;
using qif = int;
S f(dsu &uf, qif info) {
    return uf.size(info);
}

使用例

クエリとして、2頂点の連結性を問う場合。

#include "../Utility/template.hpp"
#include "../Datastructure/undabledsu.hpp"
#include "../Datastructure/offline_connectivity.hpp"

int main() {
    int n = 10;
    offline_connectivity<dsu, bool, pair<int, int>, false> uf(n); 
    /* 
      n頂点の offlien_connevtivityを宣言。　使用するdsuの型名がdsu 答えの型がbool クエリの型がpair<int, int> 多重辺無し
      この状態では、無辺のグラフ。
    */

    uf.link(0, 1);// 0, 1に辺を貼る。

    uf.query(pair<int, int>(0, 1)); // 0, 1についてクエリを飛ばす

    uf.cut(0, 1); // 0, 1辺を切る

    uf.query(pair<int, int>(0, 1)); // 0, 1についてクエリを飛ばす。


    uf.build(); //クエリを飛ばし終わったら呼ぶ。

    auto f = [&](dsu &UF, pair<int, int> query) {
        return UF.same(query.first, query.second);
    };
    //クエリを処理する関数。 dsuは参照で受け取る。

    vec<bool> res = uf.run(f); //fを引数に渡し、結果を受け取る。

    if(res[0] == true) cout << "0と1は連結だった" << endl;
    if(res[1] == false) cout << "0と1は不連結になった" << endl; 
}


注意

値の集約について : undo可能dsuに任せている。値の変更がある場合、逆元がないと出来ない。(例 : +, xor)
ただし、値変更がないならば逆元がない(max,min,gcd…)でも可能(だと考えている。この場合、undodsuの実装を少し変更する必要がある。)
自己辺に対応している。

解けない問題

クエリを処理する過程において、クエリの結果が必要となるような問題。
例 : (u, v)が今同じ連結成分かどうかで次のクエリが変化する

Required by

Verified with

Code

template<class dsu, class S, class qif, bool multi_edge>
struct offline_connectivity {
    using pii = pair<int, int>;
    using edge = array<int, 4>;
    using que = pair<int, qif>;
    int n, t, sz, qi, li;
    dsu uf;
    vec<vec<pii>> dat;
    vec<multiset<pii>> es;
    vec<edge> lrs;
    vec<que> qs;
    vec<array<ll, 3>> lz;//{t, 頂点, 作用素}  作用素がllではない場合、頑張る。
    vec<S> res;

    offline_connectivity(int N) : n(N), es(N), qi(0), li(0), t(0), sz(1), uf(N) { }

    void build() {
        rep(u, 0, n) {
            for(auto [v, l] : es[u]) {
                lrs.push_back(edge{l, t, int(u), v});
            }
        }
       
        while(sz < t) sz <<= 1;
        dat.resize(2 * sz);

        for(auto [l, r, u, v] : lrs) {
            l += sz;
            r += sz;
            while(l < r) {
                if(l & 1) dat[l++].emplace_back(u, v);
                if(r & 1) dat[--r].emplace_back(u, v);
                l >>= 1, r >>= 1;
            }
        }
    }

    TT void dfs(T f, int v) {
        for(auto [a, b] : dat[v]) uf.merge(a, b);
        if(v >= sz) {
            while(li < lz.size() && lz[li][0] == v - sz) uf.set(lz[li][1], lz[li][2]), li++;//set→ applyにする必要があるかも(dsuに合わせる)
            if(qi < qs.size() && qs[qi].first == v - sz) res.push_back(f(uf, qs[qi++].second));
        }
        else {
            dfs(f, v * 2);
            dfs(f, v * 2 + 1);
        }
        rep(i, 0, dat[v].size()) uf.undo();
    }
    

    TT vec<S> run(T f) {
        dfs(f, 1);
        return res;
    }

    void link(int u, int v) {
        if(u > v) swap(u, v);
        if(multi_edge == true) es[u].insert(pii(v, t));
        else {
            auto it = es[u].lower_bound(pii(v, -1));
            if(it != es[u].end() && (*it).first == v) return;
            es[u].insert(pii(v, t));
        }
    }

    void cut(int u, int v) {
        if(u > v) swap(u, v);
        auto it = es[u].lower_bound(pii(v, -1));
        if(it == es[u].end()) return;
        auto [tar, l] = *it;
        if(tar != v) return;
        es[u].erase(it);
        lrs.push_back(edge{l, t, u, v});
        
    }

    void query(qif q) {
        qs.push_back(que(t++, q));
    }

    void apply(int v, ll f) {
        lz.push_back({t, v, f});
    }

    void set(int v, ll f) {//ufのapplyに相当する関数名がsetだった時用
        lz.push_back({t, v, f});
    }

};
/*
S f(dsu &uf, qif q) {
    return 答え
}
をrunに渡す
&を付ける事を忘れずに（計算量こわれる）

@brief offline_connectivity
@docs doc/offline_connectivity.md
*/
#line 1 "Datastructure/offline_connectivity.hpp"
template<class dsu, class S, class qif, bool multi_edge>
struct offline_connectivity {
    using pii = pair<int, int>;
    using edge = array<int, 4>;
    using que = pair<int, qif>;
    int n, t, sz, qi, li;
    dsu uf;
    vec<vec<pii>> dat;
    vec<multiset<pii>> es;
    vec<edge> lrs;
    vec<que> qs;
    vec<array<ll, 3>> lz;//{t, 頂点, 作用素}  作用素がllではない場合、頑張る。
    vec<S> res;

    offline_connectivity(int N) : n(N), es(N), qi(0), li(0), t(0), sz(1), uf(N) { }

    void build() {
        rep(u, 0, n) {
            for(auto [v, l] : es[u]) {
                lrs.push_back(edge{l, t, int(u), v});
            }
        }
       
        while(sz < t) sz <<= 1;
        dat.resize(2 * sz);

        for(auto [l, r, u, v] : lrs) {
            l += sz;
            r += sz;
            while(l < r) {
                if(l & 1) dat[l++].emplace_back(u, v);
                if(r & 1) dat[--r].emplace_back(u, v);
                l >>= 1, r >>= 1;
            }
        }
    }

    TT void dfs(T f, int v) {
        for(auto [a, b] : dat[v]) uf.merge(a, b);
        if(v >= sz) {
            while(li < lz.size() && lz[li][0] == v - sz) uf.set(lz[li][1], lz[li][2]), li++;//set→ applyにする必要があるかも(dsuに合わせる)
            if(qi < qs.size() && qs[qi].first == v - sz) res.push_back(f(uf, qs[qi++].second));
        }
        else {
            dfs(f, v * 2);
            dfs(f, v * 2 + 1);
        }
        rep(i, 0, dat[v].size()) uf.undo();
    }
    

    TT vec<S> run(T f) {
        dfs(f, 1);
        return res;
    }

    void link(int u, int v) {
        if(u > v) swap(u, v);
        if(multi_edge == true) es[u].insert(pii(v, t));
        else {
            auto it = es[u].lower_bound(pii(v, -1));
            if(it != es[u].end() && (*it).first == v) return;
            es[u].insert(pii(v, t));
        }
    }

    void cut(int u, int v) {
        if(u > v) swap(u, v);
        auto it = es[u].lower_bound(pii(v, -1));
        if(it == es[u].end()) return;
        auto [tar, l] = *it;
        if(tar != v) return;
        es[u].erase(it);
        lrs.push_back(edge{l, t, u, v});
        
    }

    void query(qif q) {
        qs.push_back(que(t++, q));
    }

    void apply(int v, ll f) {
        lz.push_back({t, v, f});
    }

    void set(int v, ll f) {//ufのapplyに相当する関数名がsetだった時用
        lz.push_back({t, v, f});
    }

};
/*
S f(dsu &uf, qif q) {
    return 答え
}
をrunに渡す
&を付ける事を忘れずに（計算量こわれる）

@brief offline_connectivity
@docs doc/offline_connectivity.md
*/
Back to top page