sotanishy's code snippets for competitive programming
View the Project on GitHub sotanishy/cp-library-cpp
#define PROBLEM \ "https://judge.yosupo.jp/problem/dynamic_tree_vertex_set_path_composite" #include <bits/stdc++.h> #include "../../math/modint.hpp" #include "../../tree/link_cut_tree.hpp" using namespace std; using mint = Modint<998244353>; struct AffineMonoid { using T = pair<pair<mint, mint>, pair<mint, mint>>; static T id() { return {{1, 0}, {1, 0}}; } static T op(T a, T b) { return { {a.first.first * b.first.first, a.first.second * b.first.first + b.first.second}, {b.second.first * a.second.first, b.second.second * a.second.first + a.second.second}, }; } }; AffineMonoid::T flip(AffineMonoid::T a) { swap(a.first, a.second); return a; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int N, Q; cin >> N >> Q; LinkCutTree<AffineMonoid, flip> lct(N); for (int i = 0; i < N; ++i) { int a, b; cin >> a >> b; lct.set(i, {{a, b}, {a, b}}); } for (int i = 0; i < N - 1; ++i) { int u, v; cin >> u >> v; lct.link(u, v); } for (int i = 0; i < Q; ++i) { int t; cin >> t; if (t == 0) { int u, v, w, x; cin >> u >> v >> w >> x; lct.evert(u); lct.cut(v); lct.link(w, x); } else if (t == 1) { int p, c, d; cin >> p >> c >> d; lct.set(p, {{c, d}, {c, d}}); } else { int u, v, x; cin >> u >> v >> x; auto f = lct.fold(u, v); cout << f.first.first * x + f.first.second << "\n"; } } }
#line 1 "test/yosupo/dynamic_tree_vertex_set_path_composite.test.cpp" #define PROBLEM \ "https://judge.yosupo.jp/problem/dynamic_tree_vertex_set_path_composite" #include <bits/stdc++.h> #line 4 "math/modint.hpp" /** * @brief Mod int */ template <int m> class Modint { using mint = Modint; static_assert(m > 0, "Modulus must be positive"); public: static constexpr int mod() { return m; } constexpr Modint(long long y = 0) : x(y >= 0 ? y % m : (y % m + m) % m) {} constexpr int val() const { return x; } constexpr mint& operator+=(const mint& r) { if ((x += r.x) >= m) x -= m; return *this; } constexpr mint& operator-=(const mint& r) { if ((x += m - r.x) >= m) x -= m; return *this; } constexpr mint& operator*=(const mint& r) { x = static_cast<int>(1LL * x * r.x % m); return *this; } constexpr mint& operator/=(const mint& r) { return *this *= r.inv(); } constexpr bool operator==(const mint& r) const { return x == r.x; } constexpr mint operator+() const { return *this; } constexpr mint operator-() const { return mint(-x); } constexpr friend mint operator+(const mint& l, const mint& r) { return mint(l) += r; } constexpr friend mint operator-(const mint& l, const mint& r) { return mint(l) -= r; } constexpr friend mint operator*(const mint& l, const mint& r) { return mint(l) *= r; } constexpr friend mint operator/(const mint& l, const mint& r) { return mint(l) /= r; } constexpr mint inv() const { int a = x, b = m, u = 1, v = 0; while (b > 0) { int t = a / b; std::swap(a -= t * b, b); std::swap(u -= t * v, v); } return mint(u); } constexpr mint pow(long long n) const { mint ret(1), mul(x); while (n > 0) { if (n & 1) ret *= mul; mul *= mul; n >>= 1; } return ret; } friend std::ostream& operator<<(std::ostream& os, const mint& r) { return os << r.x; } friend std::istream& operator>>(std::istream& is, mint& r) { long long t; is >> t; r = mint(t); return is; } private: int x; }; #line 5 "tree/link_cut_tree.hpp" template <typename M, typename M::T (*flip)(typename M::T)> class LinkCutTree { using T = M::T; public: LinkCutTree() = default; explicit LinkCutTree(int n) { for (int i = 0; i < n; ++i) { vertex.push_back(std::make_shared<Node>(M::id())); } } void link(int v, int p) { evert(v); expose(vertex[p]); vertex[v]->par = vertex[p]; vertex[p]->right = vertex[v]; recalc(vertex[p]); } void cut(int v) { expose(vertex[v]); auto p = vertex[v]->left; vertex[v]->left = p->par = nullptr; recalc(vertex[v]); } void evert(int v) { expose(vertex[v]); reverse(vertex[v]); } int par(int v) { return vertex[v]->par ? vertex[v]->par->label : -1; } T get(int v) const { return vertex[v]->val; } void set(int v, const T& x) { expose(vertex[v]); vertex[v]->val = x; recalc(vertex[v]); } T fold(int u, int v) { evert(u); expose(vertex[v]); return vertex[v]->sum; } private: struct Node; using node_ptr = std::shared_ptr<Node>; struct Node { node_ptr left, right, par; T val, sum; int sz; bool rev; Node(const T& x) : left(nullptr), right(nullptr), par(nullptr), val(x), sum(x), sz(1), rev(false) {} }; std::vector<node_ptr> vertex; static void expose(node_ptr v) { node_ptr prev = nullptr; for (auto cur = v; cur; cur = cur->par) { splay(cur); cur->right = prev; recalc(cur); prev = cur; } splay(v); } // splay tree static int size(const node_ptr& t) { return t ? t->sz : 0; } static void recalc(const node_ptr& t) { if (!t) return; t->sz = size(t->left) + 1 + size(t->right); t->sum = t->val; if (t->left) t->sum = M::op(t->left->sum, t->sum); if (t->right) t->sum = M::op(t->sum, t->right->sum); } static void push(const node_ptr& t) { if (t->rev) { if (t->left) reverse(t->left); if (t->right) reverse(t->right); t->rev = false; } } static void reverse(const node_ptr& t) { std::swap(t->left, t->right); t->sum = flip(t->sum); t->rev ^= true; } static void rotate_left(node_ptr t) { node_ptr s = t->right; t->right = s->left; if (s->left) s->left->par = t; s->par = t->par; if (t->par) { if (t->par->left == t) { t->par->left = s; } if (t->par->right == t) { t->par->right = s; } } s->left = t; t->par = s; recalc(t); recalc(s); } static void rotate_right(node_ptr t) { node_ptr s = t->left; t->left = s->right; if (s->right) s->right->par = t; s->par = t->par; if (t->par) { if (t->par->left == t) { t->par->left = s; } if (t->par->right == t) { t->par->right = s; } } s->right = t; t->par = s; recalc(t); recalc(s); } static bool is_root(const node_ptr& t) { return !t->par || (t->par->left != t && t->par->right != t); } static void splay(node_ptr t) { push(t); while (!is_root(t)) { auto p = t->par; if (is_root(p)) { push(p); push(t); if (t == p->left) rotate_right(p); else rotate_left(p); } else { auto g = p->par; push(g); push(p); push(t); if (t == p->left) { if (p == g->left) { rotate_right(g); rotate_right(p); } else { rotate_right(p); rotate_left(g); } } else { if (p == g->left) { rotate_left(p); rotate_right(g); } else { rotate_left(g); rotate_left(p); } } } } } }; #line 8 "test/yosupo/dynamic_tree_vertex_set_path_composite.test.cpp" using namespace std; using mint = Modint<998244353>; struct AffineMonoid { using T = pair<pair<mint, mint>, pair<mint, mint>>; static T id() { return {{1, 0}, {1, 0}}; } static T op(T a, T b) { return { {a.first.first * b.first.first, a.first.second * b.first.first + b.first.second}, {b.second.first * a.second.first, b.second.second * a.second.first + a.second.second}, }; } }; AffineMonoid::T flip(AffineMonoid::T a) { swap(a.first, a.second); return a; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int N, Q; cin >> N >> Q; LinkCutTree<AffineMonoid, flip> lct(N); for (int i = 0; i < N; ++i) { int a, b; cin >> a >> b; lct.set(i, {{a, b}, {a, b}}); } for (int i = 0; i < N - 1; ++i) { int u, v; cin >> u >> v; lct.link(u, v); } for (int i = 0; i < Q; ++i) { int t; cin >> t; if (t == 0) { int u, v, w, x; cin >> u >> v >> w >> x; lct.evert(u); lct.cut(v); lct.link(w, x); } else if (t == 1) { int p, c, d; cin >> p >> c >> d; lct.set(p, {{c, d}, {c, d}}); } else { int u, v, x; cin >> u >> v >> x; auto f = lct.fold(u, v); cout << f.first.first * x + f.first.second << "\n"; } } }