data_structure/test/dynamic_graph_vertex_add_component_sum.test.cpp

• View this file on GitHub
• Last update: 2023-05-13 23:16:23+09:00
• Problem: https://judge.yosupo.jp/problem/dynamic_graph_vertex_add_component_sum

Depends on

• Offline dynamic connectivity (data_structure/offline_dynamic_connectivity.hpp)
• UnionFind with Undo operation, monoid weights （Undo 可能・重み和取得可能 UnionFind） (unionfind/undo_monoid_unionfind.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/dynamic_graph_vertex_add_component_sum"
#include "../../unionfind/undo_monoid_unionfind.hpp"
#include "../offline_dynamic_connectivity.hpp"

#include <iostream>
#include <map>
#include <utility>
using namespace std;

int main() {
    cin.tie(nullptr), ios::sync_with_stdio(false);
    int N, Q;
    cin >> N >> Q;

    using lint = long long;
    vector<lint> a(N);
    for (auto &x : a) cin >> x;

    vector<pair<int, int>> edges;
    map<pair<int, int>, pair<int, int>> edge_to_id_since;

    offline_dynamic_connectivity<std::pair<int, int>> dc; // for verification

    vector<pair<int, lint>> qs;

    vector<int> get_query;
    vector<lint> ret;
    for (int q = 0; q < Q; ++q) {
        int tp;
        cin >> tp;
        if (tp <= 1) {
            int u, v;
            cin >> u >> v;
            if (u > v) swap(u, v);

            if (tp == 0) {
                edge_to_id_since[make_pair(u, v)] = make_pair(edges.size(), q);
                edges.emplace_back(u, v);
            } else {
                int id_, since;
                tie(id_, since) = edge_to_id_since[make_pair(u, v)];
                dc.apply_time_range({since, 0}, {q, 0}, id_);
                edge_to_id_since.erase(make_pair(u, v));
            }
        } else if (tp == 2) {
            int v;
            lint x;
            cin >> v >> x;

            dc.apply_time_range({q, 0}, {1 << 30, 0}, -1 - int(qs.size()));
            qs.emplace_back(v, x);
        } else if (tp == 3) {
            int v;
            cin >> v;

            dc.add_observation({q, 0}, ret.size());
            get_query.push_back(v);
            ret.push_back(0);
        }
    }

    for (auto p : edge_to_id_since) {
        dc.apply_time_range({p.second.second, 0}, {1 << 30, 0}, p.second.first);
    }

    undo_dsu<lint> dsu(a);

    for (auto p : dc.generate()) {
        if (p.op == DyConOperation::Begins) {
            if (p.id_ >= 0) {
                auto edge = edges.at(p.id_);
                dsu.unite(edge.first, edge.second);
            } else {
                auto q = qs.at(-p.id_ - 1);
                int v = q.first, x = q.second;
                dsu.set_weight(v, dsu.sum(v) + x);
            }
        } else if (p.op == DyConOperation::Ends) {
            dsu.undo();
        } else if (p.op == DyConOperation::Event) {
            int v = get_query.at(p.id_);
            ret.at(p.id_) = dsu.sum(v);
        }
    }

    for (auto x : ret) cout << x << '\n';
}

#line 1 "data_structure/test/dynamic_graph_vertex_add_component_sum.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/dynamic_graph_vertex_add_component_sum"
#line 2 "unionfind/undo_monoid_unionfind.hpp"
#include <numeric>
#include <tuple>
#include <utility>
#include <vector>

// UnionFind, able to rewind to the previous state by undo()
template <class S> struct undo_dsu {
    std::vector<int> par, cou;
    std::vector<S> weights;
    std::vector<std::tuple<int, int, S>> history;

    explicit undo_dsu(const std::vector<S> &init)
        : par(init.size()), cou(init.size(), 1), weights(init) {
        std::iota(par.begin(), par.end(), 0);
    }
    explicit undo_dsu(int N) : undo_dsu(std::vector<S>(N, S())) {}
    undo_dsu() : undo_dsu(0) {}

    int find(int x) const { return (par[x] == x) ? x : find(par[x]); }
    bool unite(int x, int y) {
        x = find(x), y = find(y);
        if (cou[x] < cou[y]) std::swap(x, y);
        history.emplace_back(y, cou[x], weights[x]);
        return x != y ? par[y] = x, cou[x] += cou[y], weights[x] += weights[y], true : false;
    }

    void set_weight(int x, S w) {
        x = find(x);
        history.emplace_back(x, cou[x], weights[x]);
        weights[x] = w;
    }

    void undo() {
        weights[par[std::get<0>(history.back())]] = std::get<2>(history.back());
        cou[par[std::get<0>(history.back())]] = std::get<1>(history.back());
        par[std::get<0>(history.back())] = std::get<0>(history.back());
        history.pop_back();
    }

    void reset() {
        while (!history.empty()) undo();
    }

    int count(int x) const { return cou[find(x)]; }

    const S &sum(int x) const { return weights[find(x)]; }

    bool same(int x, int y) const { return find(x) == find(y); }
};
#line 2 "data_structure/offline_dynamic_connectivity.hpp"
#include <algorithm>
#include <limits>
#include <set>
#line 7 "data_structure/offline_dynamic_connectivity.hpp"

enum class DyConOperation {
    Begins = 1,
    Ends = 2,
    Event = 3,
};

template <class Tick = int> struct offline_dynamic_connectivity {

    std::vector<std::pair<Tick, int>> ops;

    struct Edge {
        Tick since;
        Tick until;
        int edge_id;
    };
    std::vector<Edge> edges;

    offline_dynamic_connectivity() = default;

    void add_observation(Tick clk, int event_id) { ops.emplace_back(clk, event_id); }

    void apply_time_range(Tick since, Tick until, int edge_id) {
        edges.push_back(Edge{since, until, edge_id});
    }

    struct Procedure {
        DyConOperation op;
        int id_;
    };

    std::vector<std::vector<Procedure>> nodes;
    std::vector<Procedure> ret_;

    void rec(int now) {
        ret_.insert(ret_.end(), nodes[now].cbegin(), nodes[now].cend());
        if (now * 2 < int(nodes.size())) rec(now * 2);
        if (now * 2 + 1 < int(nodes.size())) rec(now * 2 + 1);

        for (auto itr = nodes[now].rbegin(); itr != nodes[now].rend(); ++itr) {
            if (itr->op == DyConOperation::Begins) {
                ret_.push_back(Procedure{DyConOperation::Ends, itr->id_});
            }
        }
    }

    std::vector<Procedure> generate() {
        if (ops.empty()) return {};

        std::vector<Tick> query_ts;
        {
            query_ts.reserve(ops.size());
            for (const auto &p : ops) query_ts.push_back(p.first);
            std::sort(query_ts.begin(), query_ts.end());
            query_ts.erase(std::unique(query_ts.begin(), query_ts.end()), query_ts.end());

            std::vector<int> t_use(query_ts.size() + 1);
            t_use.at(0) = 1;

            for (const Edge &e : edges) {
                t_use[std::lower_bound(query_ts.begin(), query_ts.end(), e.since) - query_ts.begin()] =
                    1;
                t_use[std::lower_bound(query_ts.begin(), query_ts.end(), e.until) - query_ts.begin()] =
                    1;
            }
            for (int i = 1; i < int(query_ts.size()); ++i) {
                if (!t_use[i]) query_ts[i] = query_ts[i - 1];
            }

            query_ts.erase(std::unique(query_ts.begin(), query_ts.end()), query_ts.end());
        }

        const int N = query_ts.size();
        int D = 1;
        while (D < int(query_ts.size())) D *= 2;

        nodes.assign(D + N, {});

        for (const Edge &e : edges) {
            int l =
                D + (std::lower_bound(query_ts.begin(), query_ts.end(), e.since) - query_ts.begin());
            int r =
                D + (std::lower_bound(query_ts.begin(), query_ts.end(), e.until) - query_ts.begin());

            while (l < r) {
                if (l & 1) nodes[l++].push_back(Procedure{DyConOperation::Begins, e.edge_id});
                if (r & 1) nodes[--r].push_back(Procedure{DyConOperation::Begins, e.edge_id});
                l >>= 1, r >>= 1;
            }
        }

        for (const auto &op : ops) {
            int t = std::upper_bound(query_ts.begin(), query_ts.end(), op.first) - query_ts.begin();
            nodes.at(t + D - 1).push_back(Procedure{DyConOperation::Event, op.second});
        }
        ret_.clear();
        rec(1);
        return ret_;
    }
};
#line 4 "data_structure/test/dynamic_graph_vertex_add_component_sum.test.cpp"

#include <iostream>
#include <map>
#line 8 "data_structure/test/dynamic_graph_vertex_add_component_sum.test.cpp"
using namespace std;

int main() {
    cin.tie(nullptr), ios::sync_with_stdio(false);
    int N, Q;
    cin >> N >> Q;

    using lint = long long;
    vector<lint> a(N);
    for (auto &x : a) cin >> x;

    vector<pair<int, int>> edges;
    map<pair<int, int>, pair<int, int>> edge_to_id_since;

    offline_dynamic_connectivity<std::pair<int, int>> dc; // for verification

    vector<pair<int, lint>> qs;

    vector<int> get_query;
    vector<lint> ret;
    for (int q = 0; q < Q; ++q) {
        int tp;
        cin >> tp;
        if (tp <= 1) {
            int u, v;
            cin >> u >> v;
            if (u > v) swap(u, v);

            if (tp == 0) {
                edge_to_id_since[make_pair(u, v)] = make_pair(edges.size(), q);
                edges.emplace_back(u, v);
            } else {
                int id_, since;
                tie(id_, since) = edge_to_id_since[make_pair(u, v)];
                dc.apply_time_range({since, 0}, {q, 0}, id_);
                edge_to_id_since.erase(make_pair(u, v));
            }
        } else if (tp == 2) {
            int v;
            lint x;
            cin >> v >> x;

            dc.apply_time_range({q, 0}, {1 << 30, 0}, -1 - int(qs.size()));
            qs.emplace_back(v, x);
        } else if (tp == 3) {
            int v;
            cin >> v;

            dc.add_observation({q, 0}, ret.size());
            get_query.push_back(v);
            ret.push_back(0);
        }
    }

    for (auto p : edge_to_id_since) {
        dc.apply_time_range({p.second.second, 0}, {1 << 30, 0}, p.second.first);
    }

    undo_dsu<lint> dsu(a);

    for (auto p : dc.generate()) {
        if (p.op == DyConOperation::Begins) {
            if (p.id_ >= 0) {
                auto edge = edges.at(p.id_);
                dsu.unite(edge.first, edge.second);
            } else {
                auto q = qs.at(-p.id_ - 1);
                int v = q.first, x = q.second;
                dsu.set_weight(v, dsu.sum(v) + x);
            }
        } else if (p.op == DyConOperation::Ends) {
            dsu.undo();
        } else if (p.op == DyConOperation::Event) {
            int v = get_query.at(p.id_);
            ret.at(p.id_) = dsu.sum(v);
        }
    }

    for (auto x : ret) cout << x << '\n';
}

Back to top page