This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub suisen-cp/cp-library-cpp
#include "library/algorithm/offline_dynamic_connectivity_component_sum.hpp"
Offline Dynamic Connectivity で用いる Undo 可能 Union Find に連結成分の和を持たせることで実現する。
#ifndef SUISEN_OFFLINE_DYNAMIC_CONNECTIVITY_COMPONENT_SUM #define SUISEN_OFFLINE_DYNAMIC_CONNECTIVITY_COMPONENT_SUM #include <iostream> #include <map> #include <tuple> #include <variant> #include "library/datastructure/union_find/undo_union_find_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 #endif // SUISEN_OFFLINE_DYNAMIC_CONNECTIVITY_COMPONENT_SUM
#line 1 "library/algorithm/offline_dynamic_connectivity_component_sum.hpp" #include <iostream> #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