sotanishy's code snippets for competitive programming
View the Project on GitHub sotanishy/cp-library-cpp
#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"; }