test/yosupo/dynamic_graph_vertex_add_component_sum.test.cpp

• View this file on GitHub
• Last update: 2024-01-08 13:32:33+09:00
• Problem: https://judge.yosupo.jp/problem/dynamic_graph_vertex_add_component_sum

Depends on

• Undoable Union Find (data-structure/unionfind/undoable_union_find.hpp)
• Offline Dynamic Connectivity (graph/offline_dynamic_connectivity.hpp)

Code

#define PROBLEM \
    "https://judge.yosupo.jp/problem/dynamic_graph_vertex_add_component_sum"

#include <bits/stdc++.h>

#include "../../graph/offline_dynamic_connectivity.hpp"
using namespace std;

using ll = long long;

struct AddMonoid {
    using T = ll;
    static T id() { return 0; }
    static T op(T a, T b) { return a + b; }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    cin >> N >> Q;
    vector<ll> a(N);
    for (auto& x : a) cin >> x;
    OfflineDynamicConnectivity<AddMonoid> dc(a);
    for (int i = 0; i < Q; ++i) {
        int t;
        cin >> t;
        if (t == 0) {
            int u, v;
            cin >> u >> v;
            dc.link(u, v);
        }
        if (t == 1) {
            int u, v;
            cin >> u >> v;
            dc.cut(u, v);
        }
        if (t == 2) {
            int v, x;
            cin >> v >> x;
            dc.update(v, x);
        }
        if (t == 3) {
            int v;
            cin >> v;
            dc.component_fold(v);
        }
    }
    auto ans = dc.run();
    for (auto x : ans) cout << x.second << "\n";
}

#line 1 "test/yosupo/dynamic_graph_vertex_add_component_sum.test.cpp"
#define PROBLEM \
    "https://judge.yosupo.jp/problem/dynamic_graph_vertex_add_component_sum"

#include <bits/stdc++.h>

#line 3 "graph/offline_dynamic_connectivity.hpp"
#include <bit>
#line 9 "graph/offline_dynamic_connectivity.hpp"

#line 7 "data-structure/unionfind/undoable_union_find.hpp"

template <typename M>
class UndoableUnionFind {
    using T = M::T;

   public:
    UndoableUnionFind() = default;
    explicit UndoableUnionFind(int n)
        : UndoableUnionFind(std::vector<T>(n, M::id())) {}
    explicit UndoableUnionFind(const std::vector<T>& v)
        : data(v.size(), -1), val(v.begin(), v.end()) {}

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

    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        history.emplace(-1, 0, M::id());
        history.emplace(x, data[x], val[x]);
        history.emplace(y, data[y], val[y]);
        if (x == y) return;
        if (data[x] > data[y]) std::swap(x, y);
        data[x] += data[y];
        data[y] = x;
        val[x] = M::op(val[x], val[y]);
    }

    void undo() {
        assert(!history.empty());
        while (true) {
            auto [x, dx, vx] = history.top();
            history.pop();
            if (x == -1) break;
            data[x] = dx;
            val[x] = vx;
        }
    }

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

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

    T component_fold(int x) const { return val[find(x)]; }

    void update(int x, const T& v) {
        x = find(x);
        history.emplace(-1, 0, M::id());
        history.emplace(x, data[x], val[x]);
        val[x] = M::op(val[x], v);
    }

   private:
    std::vector<int> data;
    std::vector<T> val;
    std::stack<std::tuple<int, int, T>> history;
};
#line 11 "graph/offline_dynamic_connectivity.hpp"

template <typename M>
class OfflineDynamicConnectivity {
    using T = M::T;

   public:
    OfflineDynamicConnectivity() = default;
    explicit OfflineDynamicConnectivity(int n)
        : OfflineDynamicConnectivity(std::vector<T>(n, M::id())) {}
    explicit OfflineDynamicConnectivity(const std::vector<T>& v) : val(v) {}

    void link(int u, int v) {
        ++now;
        auto edge = std::minmax(u, v);
        open.emplace(edge, now);
    }

    void cut(int u, int v) {
        ++now;
        auto edge = std::minmax(u, v);
        auto it = open.find(edge);
        assert(it != open.end());
        closed.emplace_back(edge.first, edge.second, it->second, now);
        open.erase(it);
    }

    void update(int v, const T& x) {
        ++now;
        query_update.emplace_back(now, v, x);
    }

    void same(int u, int v) {
        ++now;
        query_same[now] = {u, v};
    }

    void component_fold(int v) {
        ++now;
        query_fold[now] = v;
    }

    std::vector<std::pair<bool, T>> run() {
        ++now;

        // cut edges
        for (auto [edge, s] : open) {
            closed.emplace_back(edge.first, edge.second, s, now);
        }

        // build a segment tree
        int size = std::bit_ceil((unsigned int)now);
        std::vector<std::vector<std::pair<int, int>>> edges(2 * size);
        std::vector<std::vector<std::pair<int, T>>> updates(2 * size);

        for (auto [u, v, s, t] : closed) {
            for (s += size, t += size; s < t; s >>= 1, t >>= 1) {
                if (s & 1) edges[s++].emplace_back(u, v);
                if (t & 1) edges[--t].emplace_back(u, v);
            }
        }

        for (auto [s, v, x] : query_update) {
            int t = size;
            for (s += size, t += size; s < t; s >>= 1, t >>= 1) {
                if (s & 1) updates[s++].emplace_back(v, x);
                if (t & 1) updates[--t].emplace_back(v, x);
            }
        }

        // handle queries
        UndoableUnionFind<M> uf(val);
        std::vector<std::pair<bool, T>> ret;

        auto dfs = [&](const auto& self, int k) -> void {
            for (auto [u, v] : edges[k]) {
                uf.unite(u, v);
            }
            for (auto [v, x] : updates[k]) {
                uf.update(v, x);
            }
            if (k < size) {
                self(self, 2 * k);
                self(self, 2 * k + 1);
            } else if (k < size + now) {
                if (query_same.contains(k - size)) {
                    auto [u, v] = query_same[k - size];
                    ret.emplace_back(uf.same(u, v), M::id());
                }
                if (query_fold.contains(k - size)) {
                    ret.emplace_back(false,
                                     uf.component_fold(query_fold[k - size]));
                }
            }
            for (int i = 0; i < (int)(edges[k].size() + updates[k].size());
                 ++i) {
                uf.undo();
            }
        };

        dfs(dfs, 1);
        return ret;
    }

   private:
    int now = 0;
    std::multimap<std::pair<int, int>, int> open;
    std::vector<std::tuple<int, int, int, int>> closed;
    std::vector<std::tuple<int, int, T>> query_update;
    std::map<int, std::pair<int, int>> query_same;
    std::map<int, int> query_fold;
    std::vector<T> val;
};
#line 7 "test/yosupo/dynamic_graph_vertex_add_component_sum.test.cpp"
using namespace std;

using ll = long long;

struct AddMonoid {
    using T = ll;
    static T id() { return 0; }
    static T op(T a, T b) { return a + b; }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    cin >> N >> Q;
    vector<ll> a(N);
    for (auto& x : a) cin >> x;
    OfflineDynamicConnectivity<AddMonoid> dc(a);
    for (int i = 0; i < Q; ++i) {
        int t;
        cin >> t;
        if (t == 0) {
            int u, v;
            cin >> u >> v;
            dc.link(u, v);
        }
        if (t == 1) {
            int u, v;
            cin >> u >> v;
            dc.cut(u, v);
        }
        if (t == 2) {
            int v, x;
            cin >> v >> x;
            dc.update(v, x);
        }
        if (t == 3) {
            int v;
            cin >> v;
            dc.component_fold(v);
        }
    }
    auto ans = dc.run();
    for (auto x : ans) cout << x.second << "\n";
}

Back to top page