sotanishy's code snippets for competitive programming
View the Project on GitHub sotanishy/cp-library-cpp
#define PROBLEM "https://judge.yosupo.jp/problem/range_reverse_range_sum" #include <bits/stdc++.h> #include "../../data-structure/bst/splay_tree.hpp" using namespace std; struct AddMonoid { using T = long long; 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(0); int N, Q; cin >> N >> Q; SplayTree<AddMonoid> st; for (int i = 0; i < N; ++i) { long long x; cin >> x; st.push_back(x); } for (int i = 0; i < Q; i++) { int t, l, r; cin >> t >> l >> r; if (t == 0) { st.reverse(l, r); } else { cout << st.fold(l, r) << "\n"; } } }
#line 1 "test/yosupo/range_reverse_range_sum.splay_tree.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/range_reverse_range_sum" #include <bits/stdc++.h> #line 5 "data-structure/bst/splay_tree.hpp" template <typename M> class SplayTree { using T = typename M::T; public: SplayTree() = default; static SplayTree join(SplayTree l, SplayTree r) { return SplayTree(join(std::move(l.root), std::move(r.root))); } std::pair<SplayTree, SplayTree> split(int k) { auto p = split(std::move(root), k); return {SplayTree(std::move(p.first)), SplayTree(std::move(p.second))}; } void update(int k, const T& x) { root = splay(std::move(root), k); root->val = x; recalc(root); } T fold(int l, int r) { assert(0 <= l && l <= r && r <= size()); if (l == r) return M::id(); node_ptr a, b, c; std::tie(a, b) = split(std::move(root), l); std::tie(b, c) = split(std::move(b), r - l); auto ret = b->sum; root = join(join(std::move(a), std::move(b)), std::move(c)); return ret; } void reverse(int l, int r) { assert(0 <= l && l <= r && r <= size()); if (l == r) return; node_ptr a, b, c; std::tie(a, b) = split(std::move(root), l); std::tie(b, c) = split(std::move(b), r - l); b->rev ^= true; root = join(join(std::move(a), std::move(b)), std::move(c)); } void insert(int k, const T& x) { auto p = split(std::move(root), k); root = join(join(std::move(p.first), std::make_unique<Node>(x)), std::move(p.second)); } void erase(int k) { root = splay(std::move(root), k); root = join(std::move(root->left), std::move(root->right)); } void push_front(const T& x) { root = join(std::make_unique<Node>(x), std::move(root)); } void push_back(const T& x) { root = join(std::move(root), std::make_unique<Node>(x)); } void pop_front() { root = split(std::move(root), 1).second; } void pop_back() { root = split(std::move(root), size() - 1).first; } int size() const { return size(root); } bool empty() const { return size() == 0; } private: struct Node; using node_ptr = std::unique_ptr<Node>; struct Node { node_ptr left, right; T val, sum; int sz; bool rev; Node() : Node(M::id()) {} Node(const T& x) : left(nullptr), right(nullptr), val(x), sum(x), sz(1), rev(false) {} }; node_ptr root; explicit SplayTree(node_ptr root) : root(std::move(root)) {} 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) { std::swap(t->left, t->right); if (t->left) t->left->rev ^= true; if (t->right) t->right->rev ^= true; t->rev = false; } } static node_ptr join(node_ptr l, node_ptr r) { if (!l) return r; if (!r) return l; l = splay(std::move(l), size(l) - 1); l->right = std::move(r); recalc(l); return l; } static std::pair<node_ptr, node_ptr> split(node_ptr t, int k) { assert(0 <= k && k <= size(t)); if (k == 0) return {nullptr, std::move(t)}; if (k == size(t)) return {std::move(t), nullptr}; t = splay(std::move(t), k - 1); auto r = std::move(t->right); t->right = nullptr; recalc(t); return {std::move(t), std::move(r)}; } static node_ptr rotate_left(node_ptr t) { node_ptr s = std::move(t->right); t->right = std::move(s->left); s->left = std::move(t); recalc(s->left); recalc(s); return s; } static node_ptr rotate_right(node_ptr t) { node_ptr s = std::move(t->left); t->left = std::move(s->right); s->right = std::move(t); recalc(s->right); recalc(s); return s; } static node_ptr splay(node_ptr t, int k) { assert(0 <= k && k <= size(t)); push(t); int lsize = size(t->left); if (k == lsize) return t; if (k < lsize) { push(t->left); int llsize = size(t->left->left); if (k < llsize) { t->left->left = splay(std::move(t->left->left), k); t = rotate_right(std::move(t)); } else if (llsize < k) { t->left->right = splay(std::move(t->left->right), k - llsize - 1); t->left = rotate_left(std::move(t->left)); } return rotate_right(std::move(t)); } else { push(t->right); k -= lsize + 1; int rlsize = size(t->right->left); if (k < rlsize) { t->right->left = splay(std::move(t->right->left), k); t->right = rotate_right(std::move(t->right)); } else if (rlsize < k) { t->right->right = splay(std::move(t->right->right), k - rlsize - 1); t = rotate_left(std::move(t)); } return rotate_left(std::move(t)); } } }; #line 6 "test/yosupo/range_reverse_range_sum.splay_tree.test.cpp" using namespace std; struct AddMonoid { using T = long long; 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(0); int N, Q; cin >> N >> Q; SplayTree<AddMonoid> st; for (int i = 0; i < N; ++i) { long long x; cin >> x; st.push_back(x); } for (int i = 0; i < Q; i++) { int t, l, r; cin >> t >> l >> r; if (t == 0) { st.reverse(l, r); } else { cout << st.fold(l, r) << "\n"; } } }