結果
問題 | No.235 めぐるはめぐる (5) |
ユーザー | noshi91 |
提出日時 | 2018-09-14 21:51:09 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 549 ms / 10,000 ms |
コード長 | 8,872 bytes |
コンパイル時間 | 713 ms |
コンパイル使用メモリ | 71,788 KB |
実行使用メモリ | 20,096 KB |
最終ジャッジ日時 | 2024-07-06 09:33:44 |
合計ジャッジ時間 | 4,082 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 549 ms
19,968 KB |
testcase_01 | AC | 284 ms
20,096 KB |
testcase_02 | AC | 450 ms
20,096 KB |
ソースコード
#define NDEBUG #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(); } static 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; } } } static 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); } static void reroot(const pointer ptr) { expose(ptr); reverse(ptr); } container_type nodes; pointer get_ptr(const size_type v) { return nodes.data() + v; } static pointer nil() { static node_type leaf(nullptr); return &leaf; } public: lazy_st_trees() : nodes() {} explicit lazy_st_trees(const size_type size) : nodes(size, node_type(nil())) {} bool empty() const { return nodes.empty(); } size_type size() const { return nodes.size(); } 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 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)); } }; #include <cstdint> template <::std::uint_fast32_t MODULO> class modint { using uint32 = ::std::uint_fast32_t; using uint64 = ::std::uint_fast64_t; public: using value_type = uint32; uint32 a; modint() : a(0) {} modint(const uint32 x) : a(x) {} modint operator+(const modint &o) const { return a + o.a < MODULO ? modint(a + o.a) : modint(a + o.a - MODULO); } modint operator-(const modint &o) const { return modint(a < o.a ? a + MODULO - o.a : a - o.a); } modint operator*(const modint &o) const { return modint(static_cast<uint64>(a) * o.a % MODULO); } modint operator/(const modint &o) const { return modint(static_cast<uint64>(a) * ~o % MODULO); } modint &operator+=(const modint &o) { return *this = *this + o; } modint &operator-=(const modint &o) { return *this = *this - o; } modint &operator*=(const modint &o) { return *this = *this * o; } modint &operator/=(const modint &o) { return *this = *this / o; } modint operator~() const { return pow(MODULO - 2); } modint operator-() const { return a ? modint(MODULO - a) : modint(); } modint operator++() { return a == MODULO - 1 ? a = 0 : ++a, *this; } modint operator--() { return a ? --a : a = MODULO - 1, *this; } bool operator==(const modint &o) const { return a == o.a; } bool operator!=(const modint &o) const { return a != o.a; } bool operator<(const modint &o) const { return a < o.a; } bool operator<=(const modint &o) const { return a <= o.a; } bool operator>(const modint &o) const { return a > o.a; } bool operator>=(const modint &o) const { return a >= o.a; } explicit operator bool() const { return a; } explicit operator uint32() const { return a; } modint pow(uint32 x) const { uint64 t = a, u = 1; while (x) { if (x & 1) u = u * t % MODULO; t = (t * t) % MODULO; x >>= 1; } return modint(u); } }; #include <algorithm> #include <cstddef> #include <limits> #include <utility> template <class T, class S = ::std::size_t> class sum_monoid { public: using size_type = S; using value_type = ::std::pair<T, size_type>; static value_type operation(const value_type &x, const value_type &y) { return value_type(x.first + y.first, x.second + y.second); } static value_type identity() { return value_type(T(0), S(0)); } static value_type reverse(const value_type &x) { return x; } }; template <class T> class plus_monoid { public: using value_type = T; static value_type operation(const value_type &x, const value_type &y) { return x + y; } static value_type identity() { return value_type(0); } static value_type reverse(const value_type &x) { return x; } }; template <class T, class S> class sum_plus { public: static ::std::pair<T, S> operation(const ::std::pair<T, S> &x, const T &y){ return ::std::pair<T, S>(x.first + y * x.second, x.second); } }; #include <cstdio> #include <vector> int main() { using uint = unsigned int; using mint = modint<1000000007>; using pm = std::pair<mint, mint>; uint n; scanf("%u", &n); std::vector<pm> s(n); for (auto &e : s) scanf("%u", &e.first.a); for (auto &e : s) scanf("%u", &e.second.a); lazy_st_trees<sum_monoid<mint, mint>, plus_monoid<mint>, sum_plus<mint, mint>> T(n); for (uint i = 0;i < n;++i) T.update_vertex(i, [&](auto) {return s[i];}); while (--n) { uint a, b; scanf("%u%u", &a, &b); --a;--b; T.link(a, b); } uint q; scanf("%u", &q); while (q--) { uint t, x, y; mint z; scanf("%u%u%u", &t, &x, &y); --x;--y; if (t) { printf("%u\n", T.fold_path(x, y).first.a); } else { scanf("%u", &z.a); T.update_path(x, y, mint(z)); } } return 0; }