sotanishy's code snippets for competitive programming
View the Project on GitHub sotanishy/cp-library-cpp
#define PROBLEM \ "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_B" #include <bits/stdc++.h> #include "../../data-structure/segtree/dynamic_segment_tree.hpp" using namespace std; struct Monoid { using T = int; 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; DynamicSegmentTree<Monoid> st(n); for (int i = 0; i < q; ++i) { int com, x, y; cin >> com >> x >> y; if (com == 0) st.update(x - 1, st[x - 1] + y); else cout << st.fold(x - 1, y) << "\n"; } }
#line 1 "test/aoj/DSL_2_B.dynamic_segment_tree.test.cpp" #define PROBLEM \ "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_B" #include <bits/stdc++.h> #line 2 "data-structure/segtree/dynamic_segment_tree.hpp" #include <bit> #line 4 "data-structure/segtree/dynamic_segment_tree.hpp" template <typename M> class DynamicSegmentTree { using T = M::T; public: DynamicSegmentTree() = default; explicit DynamicSegmentTree(long long n) : root(std::make_unique<Node>()), size(std::bit_ceil((unsigned long long)n)) {} T operator[](long long k) const { return fold(k, k + 1); } void update(long long k, const T& x) const { update(k, x, root, 0, size); } T fold(long long l, long long r) const { return fold(l, r, root, 0, size); } private: struct Node; using node_ptr = std::unique_ptr<Node>; struct Node { T val; node_ptr left, right; Node() : val(M::id()), left(nullptr), right(nullptr) {} }; const node_ptr root; long long size; void update(long long k, const T& x, const node_ptr& n, long long l, long long r) const { if (r - l == 1) { n->val = x; return; } long long m = std::midpoint(l, r); if (k < m) { if (!n->left) n->left = std::make_unique<Node>(); update(k, x, n->left, l, m); n->val = M::op(n->left->val, n->right ? n->right->val : M::id()); } else { if (!n->right) n->right = std::make_unique<Node>(); update(k, x, n->right, m, r); n->val = M::op(n->left ? n->left->val : M::id(), n->right->val); } } T fold(long long a, long long b, const node_ptr& n, long long l, long long r) const { if (r <= a || b <= l) return M::id(); if (a <= l && r <= b) return n->val; long long m = std::midpoint(l, r); T vl = n->left ? fold(a, b, n->left, l, m) : M::id(); T vr = n->right ? fold(a, b, n->right, m, r) : M::id(); return M::op(vl, vr); } }; #line 7 "test/aoj/DSL_2_B.dynamic_segment_tree.test.cpp" using namespace std; struct Monoid { using T = int; 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; DynamicSegmentTree<Monoid> st(n); for (int i = 0; i < q; ++i) { int com, x, y; cin >> com >> x >> y; if (com == 0) st.update(x - 1, st[x - 1] + y); else cout << st.fold(x - 1, y) << "\n"; } }