cp-library-cpp

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

View the Project on GitHub suisen-cp/cp-library-cpp

:heavy_check_mark: test/src/algorithm/offline_dynamic_connectivity_component_sum/dynamic_graph_vertex_add_component_sum.test.cpp

Depends on

Code

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

#include <iostream>

#include "library/algorithm/offline_dynamic_connectivity_component_sum.hpp"

using S = std::pair<long long, std::vector<long long>>;

void merge(S &pd, const S &cd) {
    pd.second.push_back(std::exchange(pd.first, pd.first + cd.first));
}
void undo(S &d) {
    d.first = d.second.back();
    d.second.pop_back();
}
long long get_value(const S& d) {
    return d.first;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, q;
    std::cin >> n >> q;

    std::vector<S> init_values(n);
    for (int i = 0; i < n; ++i) {
        int v;
        std::cin >> v;
        init_values[i] = { v, {} };
    }

    suisen::OfflineDynamicConnectivityComponentSum dyn_con{};
    while (q --> 0) {
        int query_type;
        std::cin >> query_type;
        if (query_type == 0) {
            int u, v;
            std::cin >> u >> v;
            dyn_con.add_query(u, v);
        } else if (query_type == 1) {
            int u, v;
            std::cin >> u >> v;
            dyn_con.del_query(u, v);
        } else if (query_type == 2) {
            int u, p;
            std::cin >> u >> p;
            dyn_con.add_query(u, init_values.size());
            init_values.push_back({ p, {} });
        } else {
            int u;
            std::cin >> u;
            dyn_con.component_sum_query(u);
        }
    }

    auto ans = dyn_con.answer<S, merge, undo, long long, get_value>(std::move(init_values));
    for (const auto &v : ans) {
        std::cout << std::get<1>(v) << '\n';
    }

    return 0;
}
#line 1 "test/src/algorithm/offline_dynamic_connectivity_component_sum/dynamic_graph_vertex_add_component_sum.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/dynamic_graph_vertex_add_component_sum"

#include <iostream>

#line 1 "library/algorithm/offline_dynamic_connectivity_component_sum.hpp"



#line 5 "library/algorithm/offline_dynamic_connectivity_component_sum.hpp"
#include <map>
#include <tuple>
#include <variant>

#line 1 "library/datastructure/union_find/undo_union_find_component_sum.hpp"



#line 1 "library/datastructure/union_find/undo_union_find.hpp"



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

namespace suisen {
    struct UndoUnionFind {
        UndoUnionFind() : UndoUnionFind(0) {}
        explicit UndoUnionFind(int n) : _n(n), _dat(n, -1) {}

        int root(int x) const {
            assert(x < _n);
            return _dat[x] < 0 ? x : root(_dat[x]);
        }
        int operator[](int x) const {
            return root(x);
        }
        bool merge(int x, int y) {
            x = root(x), y = root(y);
            if (x == y) return false;
            if (_dat[x] > _dat[y]) std::swap(x, y);
            _history.emplace_back(x, std::exchange(_dat[x], _dat[x] + _dat[y]));
            _history.emplace_back(y, std::exchange(_dat[y], x));
            return true;
        }
        bool same(int x, int y) const {
            return root(x) == root(y);
        }
        int size(int x) const {
            return -_dat[root(x)];
        }
        auto groups() const {
            std::vector<std::vector<int>> res(_n);
            for (int i = 0; i < _n; ++i) res[root(i)].push_back(i);
            res.erase(std::remove_if(res.begin(), res.end(), [](const auto &g) { return g.empty(); }), res.end());
            return res;
        }
        void snapshot() {
            _history.clear();
        }
        void undo() {
            assert(_history.size());
            _dat[_history.back().first] = _history.back().second, _history.pop_back();
            _dat[_history.back().first] = _history.back().second, _history.pop_back();
        }
        void rollback() {
            while (_history.size()) undo();
        }
    protected:
        int _n;
        std::vector<int> _dat;
        std::vector<std::pair<int, int>> _history;
    };
} // namespace suisen



#line 5 "library/datastructure/union_find/undo_union_find_component_sum.hpp"

namespace suisen {
    template <typename T, void(*merge_data)(T&, const T&), void(*undo_data)(T&)>
    struct UndoUnionFindComponentSum : UndoUnionFind {
        UndoUnionFindComponentSum() : UndoUnionFindComponentSum(0) {}
        explicit UndoUnionFindComponentSum(int n, const T &init_value = T{}) : UndoUnionFindComponentSum(std::vector<T>(n, init_value)) {}
        explicit UndoUnionFindComponentSum(const std::vector<T> &init_values) : UndoUnionFind(init_values.size()), _sum(init_values) {}

        bool merge(int x, int y) {
            x = root(x), y = root(y);
            if (x == y) return false;
            if (_dat[x] > _dat[y]) std::swap(x, y);
            _history.emplace_back(x, std::exchange(_dat[x], _dat[x] + _dat[y]));
            _history.emplace_back(y, std::exchange(_dat[y], x));
            merge_data(_sum[x], _sum[y]);
            return true;
        }
        void snapshot() {
            _history.clear();
        }
        void undo() {
            assert(_history.size());
            _dat[_history.back().first] = _history.back().second, _history.pop_back();
            undo_data(_sum[_history.back().first]);
            _dat[_history.back().first] = _history.back().second, _history.pop_back();
        }
        void rollback() {
            while (_history.size()) undo();
        }
        const T& sum(int x) const {
            return _sum[root(x)];
        }
        T& sum(int x) {
            return _sum[root(x)];
        }
    protected:
        std::vector<T> _sum;
    };
} // namespace suisen



#line 10 "library/algorithm/offline_dynamic_connectivity_component_sum.hpp"

namespace suisen {
    struct OfflineDynamicConnectivityComponentSum {
        OfflineDynamicConnectivityComponentSum() = default;

        void add_query(int u, int v) {
            _active.emplace(std::minmax(u, v), _get_queries.size());
        }
        void del_query(int u, int v) {
            auto it = _active.find(std::minmax(u, v));
            assert(it != _active.end());
            _active_range.emplace_back(u, v, it->second, _get_queries.size());
            _active.erase(it);
        }
        void connectivity_query(int u, int v) {
            _get_queries.emplace_back(u, v);
        }
        void component_sum_query(int u) {
            _get_queries.emplace_back(u, -1);
        }
        
        /**
         * if k'th get-query is a connectivity query, the index of ans[k] is 0,
         * else if k'th get-query is a component sum query, the index of ans[k] is 1.
         */
        template <typename T, void(*merge_data)(T&, const T&), void(*undo_data)(T&), typename U, U(*get_value)(const T&)>
        std::vector<std::variant<bool, U>> answer(const std::vector<T> &init_values) {
            const int q = _get_queries.size();
            for (auto it = _active.begin(); it != _active.end(); it = _active.erase(it)) {
                const auto &[u, v] = it->first;
                _active_range.emplace_back(u, v, it->second, q);
            }
            if (not q) return {};
            std::vector<std::vector<std::pair<int, int>>> seg(2 * q);
            for (auto [u, v, l, r] : _active_range) {
                for (l += q, r += q; l < r; l >>= 1, r >>= 1) {
                    if (l & 1) seg[l++].emplace_back(u, v);
                    if (r & 1) seg[--r].emplace_back(u, v);
                }
            }
            UndoUnionFindComponentSum<T, merge_data, undo_data> uf(init_values);
            std::vector<std::variant<bool, U>> ans(q);

            auto dfs = [&, this](auto dfs, int k) -> void {
                int update_counter = 0;
                for (const auto &[u, v] : seg[k]) update_counter += uf.merge(u, v);
                seg[k].clear(), seg[k].shrink_to_fit();
                if (k >= q) {
                    const int query_id = k - q;
                    const auto &[u, v] = _get_queries[query_id];
                    if (v >= 0) {
                        ans[query_id].template emplace<0>(uf.same(u, v));
                    } else {
                        ans[query_id].template emplace<1>(get_value(uf.sum(u)));
                    }
                } else {
                    dfs(dfs, 2 * k), dfs(dfs, 2 * k + 1);
                }
                while (update_counter --> 0) uf.undo();
            };
            dfs(dfs, 1);
            return ans;
        }
    private:
        std::multimap<std::pair<int, int>, int> _active;
        std::vector<std::tuple<int, int, int, int>> _active_range;
        std::vector<std::pair<int, int>> _get_queries;
    };
} // namespace suisen



#line 6 "test/src/algorithm/offline_dynamic_connectivity_component_sum/dynamic_graph_vertex_add_component_sum.test.cpp"

using S = std::pair<long long, std::vector<long long>>;

void merge(S &pd, const S &cd) {
    pd.second.push_back(std::exchange(pd.first, pd.first + cd.first));
}
void undo(S &d) {
    d.first = d.second.back();
    d.second.pop_back();
}
long long get_value(const S& d) {
    return d.first;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, q;
    std::cin >> n >> q;

    std::vector<S> init_values(n);
    for (int i = 0; i < n; ++i) {
        int v;
        std::cin >> v;
        init_values[i] = { v, {} };
    }

    suisen::OfflineDynamicConnectivityComponentSum dyn_con{};
    while (q --> 0) {
        int query_type;
        std::cin >> query_type;
        if (query_type == 0) {
            int u, v;
            std::cin >> u >> v;
            dyn_con.add_query(u, v);
        } else if (query_type == 1) {
            int u, v;
            std::cin >> u >> v;
            dyn_con.del_query(u, v);
        } else if (query_type == 2) {
            int u, p;
            std::cin >> u >> p;
            dyn_con.add_query(u, init_values.size());
            init_values.push_back({ p, {} });
        } else {
            int u;
            std::cin >> u;
            dyn_con.component_sum_query(u);
        }
    }

    auto ans = dyn_con.answer<S, merge, undo, long long, get_value>(std::move(init_values));
    for (const auto &v : ans) {
        std::cout << std::get<1>(v) << '\n';
    }

    return 0;
}
Back to top page