verify/Datastructure_value_dsu.test.cpp

• View this file on GitHub
• Last update: 2025-01-10 00:00:54+09:00
• Problem: https://judge.yosupo.jp/problem/dynamic_graph_vertex_add_component_sum

Depends on

• offline_connectivity (Datastructure/offline_connectivity.hpp)
• 値集約・変更可能なdsu (Datastructure/value_dsu.hpp)
• verify用テンプレート (Utility/template.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/dynamic_graph_vertex_add_component_sum"
#include "../Utility/template.hpp"
#include "../Datastructure/value_dsu.hpp"
#include "../Datastructure/offline_connectivity.hpp"

using S = ll;
S op(S l, S r) {
    return l + r;
}

S e() {
    return 0LL;
}


S f(dsu<S, op, e> &uf, int v) {
    return uf.get(v);
}

int main() {
    int n, q;
    cin >> n >> q;
    vec<ll> A(n);
    rep(i, 0, n) cin >> A[i];
    offline_connectivity<dsu<S, op, e>, S, int, false> uf(n);
    rep(i, 0, n) uf.set(i, A[i]);

    while(q--) {
        int t;
        cin >> t;
        if(t == 0) {
            int u, v;
            cin >> u >> v;
            uf.link(u, v);
        }
        else if(t == 1) {
            int u, v;
            cin >> u >> v;
            uf.cut(u, v);
        }
        else if(t == 2) {
            int v; ll x;
            cin >> v >> x;
            A[v] += x;
            uf.set(v, A[v]);
        }
        else {
            int v;
            cin >> v;
            uf.query(v);
        }
    }

    uf.build();
    auto res = uf.run(f);
    for(ll x : res) cout << x << "\n";


}

#line 1 "verify/Datastructure_value_dsu.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/dynamic_graph_vertex_add_component_sum"
#line 1 "Utility/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, s, t) for (ll i = s; i < (ll)(t); i++)
#define rrep(i, s, t) for (ll i = (ll)(t) - 1; i >= (ll)(s); i--)
#define all(x) begin(x), end(x)

#define TT template <typename T>
TT using vec = vector<T>;
template <class T1, class T2> bool chmin(T1 &x, T2 y) {
    return x > y ? (x = y, true) : false;
}
template <class T1, class T2> bool chmax(T1 &x, T2 y) {
    return x < y ? (x = y, true) : false;
}
struct io_setup {
    io_setup() {
        ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
        cout << fixed << setprecision(15);
    }
} io_setup;

/*
@brief verify用テンプレート
*/
#line 1 "Datastructure/value_dsu.hpp"
template<class S, S (*op)(S, S), S (*e) ()> struct dsu {
    using vi = vec<int>;
    using vvi = vec<vi>;   

    struct dat {
        int r, u, v, p;
        dat(){}
        dat(int a, int b, int c, int d) : r(a), u(b), v(c), p(d) {}
    };
   
    int cc;
    vi par, sz, es, lv, lch, rch, rank;
    vec<S> A, acc;
    stack<dat> his;
   

    dsu(int n) {
        cc = n;
        par = vi(n);
        lv = rank = es = vi(n, 0);
        sz = vi(n, 1);
        lch = rch = vi(n, -1);
        A = acc = vec<S>(n, e());
        iota(all(par), 0);
    }
  
    int leader(int u) {
        while(par[u] != u) {
            u = par[u];
        }
        return u;
    }
    
    bool same(int a, int b) {
        return leader(a) == leader(b);
    }

    int update(int v) {
        while(1) {
            if(rch[v] != -1) {
                lv[v] = min(lv[lch[v]], lv[rch[v]]) + 1;
                acc[v] = op(A[v], op(acc[lch[v]], acc[rch[v]]));
            }
            else if(lch[v] != -1) {
                lv[v] = 0;
                acc[v] = op(A[v], acc[lch[v]]);
            }
            else {
                lv[v] = 0;
                acc[v] = A[v];
            }
            if(v == par[v]) break;
            v = par[v];
        }
        return v;
    }

    
    bool merge(int a, int b) {
        a = leader(a), b = leader(b);
    
        if(max(rank[a], rank[b] + lv[a] + 1)  > max(rank[b], rank[a] + lv[b] + 1)) swap(a, b);
     
        if(a == b) {
            es[a]++;
            his.push(dat(a, -1, -1, -1));
            return false;
        }

        cc--;
        int r = a;
        int p = rank[a];
        rank[a] = max(rank[a], lv[a] + rank[b] + 1);
        sz[a] += sz[b];
        es[a] += es[b] + 1;

        while(lch[a] != -1 && rch[a] != -1) {
            if(lv[lch[a]] < lv[rch[a]]) a = lch[a];
            else a = rch[a];
        }

        par[b] = a;
        if(lch[a] == -1) lch[a] = b;
        else rch[a] = b;
        his.push(dat(r, a, b, p));
        update(a);
        return true;
    }

    bool undo () {
        if(his.empty()) return false;
        dat pre = his.top();
        his.pop();
        es[pre.r]--;

        if(pre.u >= 0) {
            cc++;
            sz[pre.r] -= sz[pre.v];
            es[pre.r] -= es[pre.v];
            rank[pre.r] = pre.p;
            par[pre.v] = pre.v;
            if(lch[pre.u] == pre.v) lch[pre.u] = -1;
            else rch[pre.u] = -1;
            update(pre.u);
        }
        return true;
    }

    S get(int u) {
        return acc[leader(u)];
    }

    void set(int u, S s) {
        A[u] = s;
        update(u);
    }

    int size(int u) {//uが含まれる連結成分のサイズを返す
        return sz[leader(u)];
    }

    int edgecnt(int u) {
        return es[leader(u)];
    }

    int component_count() {
        return cc;
    }

    vvi groups() {
        int n = par.size();
        vvi ms(n);
        rep(v, 0, n) {
            ms[leader(v)].push_back(v);
        }

        vvi res;
        rep(i, 0, n) if(ms[i].size() > 0) {
            res.push_back(ms[i]);
        }
        return res;
    }
};

/*
@brief 値集約・変更可能なdsu
@docs doc/value_dsu.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
*/
#line 5 "verify/Datastructure_value_dsu.test.cpp"

using S = ll;
S op(S l, S r) {
    return l + r;
}

S e() {
    return 0LL;
}


S f(dsu<S, op, e> &uf, int v) {
    return uf.get(v);
}

int main() {
    int n, q;
    cin >> n >> q;
    vec<ll> A(n);
    rep(i, 0, n) cin >> A[i];
    offline_connectivity<dsu<S, op, e>, S, int, false> uf(n);
    rep(i, 0, n) uf.set(i, A[i]);

    while(q--) {
        int t;
        cin >> t;
        if(t == 0) {
            int u, v;
            cin >> u >> v;
            uf.link(u, v);
        }
        else if(t == 1) {
            int u, v;
            cin >> u >> v;
            uf.cut(u, v);
        }
        else if(t == 2) {
            int v; ll x;
            cin >> v >> x;
            A[v] += x;
            uf.set(v, A[v]);
        }
        else {
            int v;
            cin >> v;
            uf.query(v);
        }
    }

    uf.build();
    auto res = uf.run(f);
    for(ll x : res) cout << x << "\n";


}

Back to top page