Submit Info #2264

Problem Lang User Status Time Memory
Dynamic Tree Vertex Add Path Sum cpp noshi91 AC 529 ms 10.62 MiB

ケース詳細
Name Status Time Memory
example_00 AC 2 ms 0.67 MiB
max_random_00 AC 529 ms 10.54 MiB
max_random_01 AC 518 ms 10.55 MiB
max_random_02 AC 517 ms 10.62 MiB
random_00 AC 334 ms 7.05 MiB
random_01 AC 363 ms 8.17 MiB
random_02 AC 207 ms 3.51 MiB
random_03 AC 218 ms 8.35 MiB
random_04 AC 131 ms 1.75 MiB
small_00 AC 2 ms 0.72 MiB
small_01 AC 2 ms 0.68 MiB
small_02 AC 1 ms 0.68 MiB

#include <cassert> #include <cstddef> #include <memory> #include <utility> #include <vector> template <class ValueMonoid, class OperatorMonoid, class Modifier> class lazy_st_trees { public: using value_structure = ValueMonoid; using value_type = typename value_structure::value_type; using operator_structure = OperatorMonoid; using operator_type = typename operator_structure::value_type; using modifier = Modifier; private: class node_type { public: node_type *left, *right, *parent; typename lazy_st_trees::value_type value, sum; typename lazy_st_trees::operator_type lazy; bool reversed; // reverse->lazy node_type(node_type *const p) : left(p), right(p), parent(p), value(value_structure::identity()), sum(value_structure::identity()), lazy(operator_structure::identity()), reversed(0) {} }; using container_type = ::std::vector<node_type>; public: using size_type = typename container_type::size_type; private: using pointer = node_type *; using const_pointer = const node_type *; static void reverse(const pointer ptr) { ptr->lazy = operator_structure::reverse(::std::move(ptr->lazy)); ptr->reversed ^= 1; } static void push(const pointer ptr) { if (ptr->reversed) { ptr->reversed = 0; ptr->value = value_structure::reverse(::std::move(ptr->value)); ::std::swap(ptr->left, ptr->right); reverse(ptr->left); reverse(ptr->right); } ptr->left->lazy = operator_structure::operation(ptr->left->lazy, ptr->lazy); ptr->right->lazy = operator_structure::operation(ptr->right->lazy, ptr->lazy); ptr->value = modifier::operation(ptr->value, ptr->lazy); ptr->lazy = operator_structure::identity(); } void propagate(pointer ptr) { pointer prev = nullptr; while (ptr != nil()) { ::std::swap(ptr->parent, prev); ::std::swap(ptr, prev); } while (prev) { push(prev); ::std::swap(prev->parent, ptr); ::std::swap(prev, ptr); } nil()->sum = value_structure::identity(); nil()->lazy = operator_structure::identity(); nil()->reversed = 0; } static value_type reflect(const const_pointer ptr) { return modifier::operation( ptr->reversed ? value_structure::reverse(ptr->sum) : ptr->sum, ptr->lazy); } static void calc(const pointer ptr) { ptr->sum = value_structure::operation( value_structure::operation(reflect(ptr->left), ptr->value), reflect(ptr->right)); } static void rotate_l(const pointer ptr, const pointer ch) { ptr->right = ch->left; ch->left->parent = ptr; calc(ptr); ch->left = ptr; ptr->parent = ch; } static void rotate_r(const pointer ptr, const pointer ch) { ptr->left = ch->right; ch->right->parent = ptr; calc(ptr); ch->right = ptr; ptr->parent = ch; } static void splay(const pointer ptr) { for (pointer x, y = ptr;;) { x = ptr->parent; if (x->left == y) { y = x->parent; ptr->parent = y->parent; if (y->left == x) rotate_r(y, x), rotate_r(x, ptr); else if (y->right == x) rotate_l(y, ptr), rotate_r(x, ptr); else return ptr->parent = y, rotate_r(x, ptr); } else if (x->right == y) { y = x->parent; ptr->parent = y->parent; if (y->right == x) rotate_l(y, x), rotate_l(x, ptr); else if (y->left == x) rotate_r(y, ptr), rotate_l(x, ptr); else return ptr->parent = y, rotate_l(x, ptr); } else { return; } } } void expose(const pointer ptr) { propagate(ptr); pointer x = ptr, prev = nil(); while (x != nil()) { splay(x); x->right = prev; calc(x); prev = x; x = x->parent; } splay(ptr); calc(ptr); } void reroot(const pointer ptr) { expose(ptr); reverse(ptr); } container_type nodes; pointer get_ptr(const size_type v) { return nodes.data() + v; } pointer nil() { return &nodes.back(); } public: lazy_st_trees() : nodes() {} explicit lazy_st_trees(const size_type size) : nodes() { nodes.reserve(size + 1); nodes.resize(size + 1, node_type(nodes.data() + size)); } bool empty() const { return size() == 0; } size_type size() const { return nodes.size() - 1; } bool connected(const size_type v, const size_type u) { assert(v < size()); assert(u < size()); expose(get_ptr(v)); expose(get_ptr(u)); return nodes[v].parent != nil() || v == u; } value_type fold_path(const size_type v, const size_type u) { assert(v < size()); assert(u < size()); assert(connected(v, u)); reroot(get_ptr(v)); expose(get_ptr(u)); return nodes[u].sum; } void reroot(const size_type v) { assert(v < size()); reroot(get_ptr(v)); } void link(const size_type parent, const size_type child) { assert(parent < size()); assert(child < size()); assert(!connected(parent, child)); reroot(get_ptr(child)); nodes[child].parent = get_ptr(parent); } void cut(const size_type v) { assert(v < size()); expose(get_ptr(v)); nodes[v].left->parent = nil(); nodes[v].left = nil(); nodes[v].sum = nodes[v].value; } void update_path(const size_type v, const size_type u, const operator_type &value) { assert(v < size()); assert(u < size()); assert(connected(v, u)); reroot(get_ptr(v)); expose(get_ptr(u)); nodes[u].lazy = value; } template <class F> void update_vertex(const size_type v, const F &f) { assert(v < size()); expose(get_ptr(v)); nodes[v].value = f(::std::move(nodes[v].value)); calc(get_ptr(v)); } }; template <class T> class plus_monoid { public: using value_type = T; static constexpr T operation(const T &x, const T &y) noexcept { return x + y; } static constexpr T identity() noexcept { return 0; } static constexpr T reverse(const T &x) noexcept { return x; } }; #include <tuple> class trivial_group { public: using value_type = std::tuple<>; static constexpr value_type operation(const value_type, const value_type) noexcept { return value_type(); } static constexpr value_type identity() noexcept { return value_type(); } static constexpr value_type inverse(const value_type) noexcept { return value_type(); } static constexpr value_type reverse(const value_type) noexcept { return value_type(); } }; template <class T> class trivial_action { public: static constexpr T operation(const T &lhs, const typename trivial_group::value_type) noexcept { return lhs; } }; #include <iostream> int main() { using u64 = unsigned long long; int n, q; std::cin >> n >> q; lazy_st_trees<plus_monoid<u64>, trivial_group, trivial_action<u64>> lst(n); for (int i = 0; i != n; i += 1) { u64 a; std::cin >> a; lst.update_vertex(i, [&](auto) { return a; }); } for (int i = 0; i != n - 1; i += 1) { int u, v; std::cin >> u >> v; lst.link(u, v); } for (int i = 0; i != q; i += 1) { int t; std::cin >> t; switch (t) { case 0: { int u, v, w, x; std::cin >> u >> v >> w >> x; lst.reroot(u); lst.cut(v); lst.link(w, x); } break; case 1: { int p; u64 x; std::cin >> p >> x; lst.update_vertex(p, [&](u64 y) { return y + x; }); } break; case 2: { int u, v; std::cin >> u >> v; std::cout << lst.fold_path(u, v) << std::endl; } break; } } return 0; }