This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub suisen-cp/cp-library-cpp
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A" #include <iostream> #include <numeric> #include <random> #include "library/tree/point_set_range_contour_sum.hpp" int op(int x, int y) { return std::max(x, y); } int e() { return 0; } using Solution = suisen::PointSetRangeContourSum<int, op, e>; struct NaiveSolution { NaiveSolution(std::vector<std::vector<int>> g, std::vector<int> dat) : g(g), dat(dat) {} void set(int u, int val) { dat[u] = val; } int prod(int k, int dl, int dr) { int res = e(); auto dfs = [&](auto dfs, int u, int p, int dep) -> void { if (dl <= dep and dep < dr) res = op(res, dat[u]); for (int v : g[u]) { if (v == p) continue; dfs(dfs, v, u, dep + 1); } }; dfs(dfs, k, -1, 0); return res; } private: std::vector<std::vector<int>> g; std::vector<int> dat; }; void random_queries(int n, int q, Solution& t1, NaiveSolution& t2) { auto check = [&](int k, int dl, int dr) { int sum1 = t1.sum(k, dl, dr); int sum2 = t2.prod(k, dl, dr); assert(sum1 == sum2); }; std::mt19937 rng{ std::random_device{}() }; while (q-- > 0) { int qt = rng(); if (qt == 1) { int i = rng() % n; int v = rng() % 10000; t1.set(i, v); t2.set(i, v); } else { int i = rng() % n; int l = rng() % n; int r = l + rng() % (n - l); check(i, l, r); } } } #include <atcoder/dsu> std::vector<std::vector<int>> random_tree(int n) { std::mt19937 rng{ std::random_device{}() }; std::vector<std::pair<int, int>> edges; for (int i = 0; i < n; ++i) for (int j = 0; j < i; ++j) { edges.emplace_back(i, j); } std::shuffle(edges.begin(), edges.end(), rng); std::vector<std::vector<int>> g(n); atcoder::dsu uf(n); int con = n; while (con > 1) { auto [u, v] = edges.back(); edges.pop_back(); if (uf.same(u, v)) continue; uf.merge(u, v); --con; g[u].push_back(v); g[v].push_back(u); } return g; } void test1(int q = 100000) { std::vector<std::vector<int>> g{ { 1, 8, 16 }, // 0 { 0, 2, 3 }, // 1 { 1 }, // 2 { 1, 4, 7 }, // 3 { 3, 5, 6 }, // 4 { 4 }, // 5 { 4 }, // 6 { 3 }, // 7 { 0, 9, 10 }, // 8 { 8 }, // 9 { 8, 11, 15 }, // 10 { 10, 12, 13, 14 }, // 11 { 11 }, // 12 { 11 }, // 13 { 11 }, // 14 { 10 }, // 15 { 0, 17, 18, 20 }, // 16 { 16 }, // 17 { 16, 19 }, // 18 { 18 }, // 19 { 16, 21, 24 }, // 20 { 20, 22, 23 }, // 21 { 21 }, // 22 { 21 }, // 23 { 20 } // 24 }; const int n = g.size(); std::vector<int> dat(n); std::iota(dat.begin(), dat.end(), 1); suisen::PointSetRangeContourSum<int, op, e> contour_aggregator(dat); for (int i = 0; i < n; ++i) for (int j : g[i]) if (i < j) { contour_aggregator.add_edge(i, j); } contour_aggregator.build(); NaiveSolution naive(g, dat); random_queries(n, q, contour_aggregator, naive); } void test2(int n = 1000, int q = 10000) { auto g = random_tree(n); std::vector<int> dat(n); std::iota(dat.begin(), dat.end(), 1); suisen::PointSetRangeContourSum<int, op, e> contour_aggregator(dat); for (int i = 0; i < n; ++i) for (int j : g[i]) if (i < j) { contour_aggregator.add_edge(i, j); } contour_aggregator.build(); NaiveSolution naive(g, dat); random_queries(n, q, contour_aggregator, naive); } int main() { test1(); test2(); std::cout << "Hello World" << std::endl; return 0; }
#line 1 "test/src/tree/point_set_range_contour_sum/dummy.test.cpp" #define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A" #include <iostream> #include <numeric> #include <random> #line 1 "library/tree/point_set_range_contour_sum.hpp" #include <array> #include <cstdint> #include <deque> #include <map> #include <queue> #include <tuple> #include <utility> #include <atcoder/segtree> namespace suisen { template <typename T, T(*op)(T, T), T(*e)()> struct PointSetRangeContourSum { PointSetRangeContourSum() = default; PointSetRangeContourSum(int n, const T &fill_value) : PointSetRangeContourSum(std::vector<T>(n, fill_value)) {} PointSetRangeContourSum(const std::vector<T> &dat) : _n(dat.size()), _g(_n), _par(_n, -1), _removed(_n, false), _info(_n), _nodes(_n), _dat(dat) { _par.reserve(2 * _n); for (int i = 0; i < _n; ++i) _info[i].reserve(30); } using segtree_type = atcoder::segtree<T, op, e>; struct AuxData { int segtree_index; int8_t child_index; int dep; }; struct Node { std::vector<int> _sep; segtree_type _seq; Node() = default; Node(const std::vector<std::vector<int>>& g, const std::vector<int8_t>& removed, const std::vector<int> &roots, const bool child_index, std::vector<std::vector<AuxData>>& info, const std::vector<T> &dat, int siz) { std::vector<T> reordered_dat(siz); _sep.push_back(0); std::deque<std::tuple<int, int, int>> dq; for (int r : roots) dq.emplace_back(r, -1, 0); int pre_dist = 0, cnt = 0; while (dq.size()) { const auto [u, pu, du] = dq.front(); dq.pop_front(); if (du == pre_dist + 1) _sep.push_back(cnt), pre_dist = du; info[u].push_back({ cnt, child_index, du }); reordered_dat[cnt++] = dat[u]; for (int v : g[u]) if (v != pu and not removed[v]) dq.emplace_back(v, u, du + 1); } _sep.push_back(cnt); _seq = segtree_type(reordered_dat); } void set(int i, const T& val) { _seq.set(i, val); } T sum(int dl, int dr) const { dl = std::max(dl, 0); dr = std::min(dr, int(_sep.size()) - 1); return dl < dr ? _seq.prod(_sep[dl], _sep[dr]) : e(); } }; void add_edge(int u, int v) { _g[u].push_back(v); _g[v].push_back(u); } void build() { std::vector<int> sub_size(_n, 0); std::vector<int> ctr(_n, -1); sub_size.reserve(2 * _n); ctr.reserve(2 * _n); std::vector<std::vector<int>> ch(_n); ch.reserve(2 * _n); auto merge = [&](std::vector<int> &&l, std::vector<int> &&r) -> std::vector<int>&& { if (l.size() > r.size()) std::swap(l, r); for (int v : l) r.push_back(v); return std::move(r); }; auto rec = [&](auto rec, int r, int siz) -> int { int c = -1; auto get_centroid = [&](auto get_centroid, int u, int p) -> void { sub_size[u] = 1; for (int v : _g[u]) { if (v == p or _removed[v]) continue; get_centroid(get_centroid, v, u); if (v == c) { sub_size[u] = siz - sub_size[c]; break; } sub_size[u] += sub_size[v]; } if (c < 0 and sub_size[u] * 2 > siz) c = u; }; get_centroid(get_centroid, r, -1); _removed[c] = true; for (int v : _g[c]) { if (_removed[v]) continue; const int comp_size = sub_size[v]; ctr[v] = rec(rec, v, comp_size); sub_size[v] = comp_size; } auto comp = [&](int i, int j) { return sub_size[i] > sub_size[j]; }; std::priority_queue<int, std::vector<int>, decltype(comp)> pq{ comp }; for (int v : _g[c]) { if (_removed[v]) continue; ch[v] = { v }; pq.push(v); } while (pq.size() >= 2) { const int u = pq.top(); pq.pop(); const int v = pq.top(); pq.pop(); if (pq.empty()) { _par[ctr[u]] = _par[ctr[v]] = c; _nodes[c][0] = Node{ _g, _removed, ch[u], 0, _info, _dat, sub_size[u] }; _nodes[c][1] = Node{ _g, _removed, ch[v], 1, _info, _dat, sub_size[v] }; break; } const int new_node = sub_size.size(); sub_size.push_back(sub_size[u] + sub_size[v]); ctr.push_back(new_node); _par.push_back(-1); _par[ctr[u]] = _par[ctr[v]] = new_node; _nodes.emplace_back(); _nodes[new_node][0] = Node{ _g, _removed, ch[u], 0, _info, _dat, sub_size[u] }; _nodes[new_node][1] = Node{ _g, _removed, ch[v], 1, _info, _dat, sub_size[v] }; ch.push_back(merge(std::move(ch[u]), std::move(ch[v]))); ch[u].clear(), ch[u].shrink_to_fit(); ch[v].clear(), ch[v].shrink_to_fit(); pq.push(new_node); } if (pq.size()) { int u = pq.top(); pq.pop(); _par[ctr[u]] = c; _nodes[c][0] = Node{ _g, _removed, ch[u], 0, _info, _dat, sub_size[u] }; } _removed[c] = false; return c; }; rec(rec, 0, _n); } T get(int u) const { return _dat[u]; } void set(int u, const T& val) { _dat[u] = val; int v = _par[u]; for (const auto &info : _info[u]) { _nodes[std::exchange(v, _par[v])][info.child_index].set(info.segtree_index, val); } } T sum(int u, int dl, int dr) const { T res = dl <= 0 and 0 < dr ? _dat[u] : e(); res = op(res, _nodes[u][0].sum(dl - 1, dr - 1)); res = op(res, _nodes[u][1].sum(dl - 1, dr - 1)); int v = _par[u]; for (const auto &info : _info[u]) { int ql = dl - info.dep - 2, qr = dr - info.dep - 2; if (v < _n and ql <= -1 and -1 < qr) res = op(res, _dat[v]); res = op(res, _nodes[std::exchange(v, _par[v])][info.child_index ^ 1].sum(ql, qr)); } return res; } private: int _n; std::vector<std::vector<int>> _g; std::vector<int> _par; std::vector<int8_t> _removed; std::vector<std::vector<AuxData>> _info; std::vector<std::array<Node, 2>> _nodes; std::vector<T> _dat; }; } // namespace suisen #line 8 "test/src/tree/point_set_range_contour_sum/dummy.test.cpp" int op(int x, int y) { return std::max(x, y); } int e() { return 0; } using Solution = suisen::PointSetRangeContourSum<int, op, e>; struct NaiveSolution { NaiveSolution(std::vector<std::vector<int>> g, std::vector<int> dat) : g(g), dat(dat) {} void set(int u, int val) { dat[u] = val; } int prod(int k, int dl, int dr) { int res = e(); auto dfs = [&](auto dfs, int u, int p, int dep) -> void { if (dl <= dep and dep < dr) res = op(res, dat[u]); for (int v : g[u]) { if (v == p) continue; dfs(dfs, v, u, dep + 1); } }; dfs(dfs, k, -1, 0); return res; } private: std::vector<std::vector<int>> g; std::vector<int> dat; }; void random_queries(int n, int q, Solution& t1, NaiveSolution& t2) { auto check = [&](int k, int dl, int dr) { int sum1 = t1.sum(k, dl, dr); int sum2 = t2.prod(k, dl, dr); assert(sum1 == sum2); }; std::mt19937 rng{ std::random_device{}() }; while (q-- > 0) { int qt = rng(); if (qt == 1) { int i = rng() % n; int v = rng() % 10000; t1.set(i, v); t2.set(i, v); } else { int i = rng() % n; int l = rng() % n; int r = l + rng() % (n - l); check(i, l, r); } } } #include <atcoder/dsu> std::vector<std::vector<int>> random_tree(int n) { std::mt19937 rng{ std::random_device{}() }; std::vector<std::pair<int, int>> edges; for (int i = 0; i < n; ++i) for (int j = 0; j < i; ++j) { edges.emplace_back(i, j); } std::shuffle(edges.begin(), edges.end(), rng); std::vector<std::vector<int>> g(n); atcoder::dsu uf(n); int con = n; while (con > 1) { auto [u, v] = edges.back(); edges.pop_back(); if (uf.same(u, v)) continue; uf.merge(u, v); --con; g[u].push_back(v); g[v].push_back(u); } return g; } void test1(int q = 100000) { std::vector<std::vector<int>> g{ { 1, 8, 16 }, // 0 { 0, 2, 3 }, // 1 { 1 }, // 2 { 1, 4, 7 }, // 3 { 3, 5, 6 }, // 4 { 4 }, // 5 { 4 }, // 6 { 3 }, // 7 { 0, 9, 10 }, // 8 { 8 }, // 9 { 8, 11, 15 }, // 10 { 10, 12, 13, 14 }, // 11 { 11 }, // 12 { 11 }, // 13 { 11 }, // 14 { 10 }, // 15 { 0, 17, 18, 20 }, // 16 { 16 }, // 17 { 16, 19 }, // 18 { 18 }, // 19 { 16, 21, 24 }, // 20 { 20, 22, 23 }, // 21 { 21 }, // 22 { 21 }, // 23 { 20 } // 24 }; const int n = g.size(); std::vector<int> dat(n); std::iota(dat.begin(), dat.end(), 1); suisen::PointSetRangeContourSum<int, op, e> contour_aggregator(dat); for (int i = 0; i < n; ++i) for (int j : g[i]) if (i < j) { contour_aggregator.add_edge(i, j); } contour_aggregator.build(); NaiveSolution naive(g, dat); random_queries(n, q, contour_aggregator, naive); } void test2(int n = 1000, int q = 10000) { auto g = random_tree(n); std::vector<int> dat(n); std::iota(dat.begin(), dat.end(), 1); suisen::PointSetRangeContourSum<int, op, e> contour_aggregator(dat); for (int i = 0; i < n; ++i) for (int j : g[i]) if (i < j) { contour_aggregator.add_edge(i, j); } contour_aggregator.build(); NaiveSolution naive(g, dat); random_queries(n, q, contour_aggregator, naive); } int main() { test1(); test2(); std::cout << "Hello World" << std::endl; return 0; }