sotanishy's code snippets for competitive programming
View the Project on GitHub sotanishy/cp-library-cpp
#include "graph/offline_dynamic_connectivity.hpp"
グラフに対する以下のクエリをオフラインで処理する:
Undo 可能 union find を用いることでこれらの操作を実現する.
空間計算量: $O(n + q\log q)$, $q$ はクエリ数
OfflineDynamicConnectivity(int n)
n
OfflineDynamicConnectivity(vector<T> v)
n = v.size()
v
void link(int u, int v)
void cut(int u, int v)
void update(int v, T x)
void same(int u, int v)
void component_fold(int v)
vector<pair<bool, T>> run()
same
component_fold
{same の結果, M::id()}
{false, component_fold の結果}
#pragma once #include <algorithm> #include <bit> #include <cassert> #include <map> #include <tuple> #include <utility> #include <vector> #include "../data-structure/unionfind/undoable_union_find.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 2 "graph/offline_dynamic_connectivity.hpp" #include <algorithm> #include <bit> #include <cassert> #include <map> #include <tuple> #include <utility> #include <vector> #line 4 "data-structure/unionfind/undoable_union_find.hpp" #include <stack> #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; };