This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub toyama1710/cpp_library
#define PROBLEM \ "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_E" #include <iostream> #include "../../segment_tree/dual_segment_tree.hpp" using namespace std; using llong = long long; struct RAQ { using value_type = long long; using T = value_type; inline static T identity() { return 0; }; inline static T operation(T a, T b) { return a + b; }; }; int main() { llong n, q; llong com; llong s, t, x; llong idx; cin >> n >> q; DualSegmentTree<RAQ> seg(n); for (int i = 0; i < q; i++) { cin >> com; if (com == 0) { cin >> s >> t >> x; s--; seg.update(s, t, x); } else if (com == 1) { cin >> idx; idx--; cout << seg[idx] << '\n'; } } };
#line 1 "test/aoj/DSL2E.test.cpp" #define PROBLEM \ "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_E" #include <iostream> #line 1 "segment_tree/dual_segment_tree.hpp" #include <cstdint> #include <vector> //=== template <class Monoid> struct DualSegmentTree { using T = typename Monoid::value_type; std::vector<T> lazy; DualSegmentTree() = default; explicit DualSegmentTree(uint32_t n) : lazy(n << 1, Monoid::identity()){}; inline int size() { return (int)(lazy.size() >> 1); }; inline void propagate(uint32_t k) { if (k >= size()) return; lazy[(k << 1) | 0] = Monoid::operation(lazy[(k << 1) | 0], lazy[k]); lazy[(k << 1) | 1] = Monoid::operation(lazy[(k << 1) | 1], lazy[k]); lazy[k] = Monoid::identity(); }; inline void push_down(uint32_t k) { for (uint32_t i = 31; i > 0; i--) propagate(k >> i); }; // [l, r) void update(uint32_t l, uint32_t r, T op) { l += size(); r += size(); push_down(l); push_down(r - 1); while (l < r) { if (l & 1) lazy[l] = Monoid::operation(lazy[l], op), l++; if (r & 1) --r, lazy[r] = Monoid::operation(lazy[r], op); l >>= 1; r >>= 1; } }; T get(uint32_t k) { k += size(); push_down(k); return lazy[k]; }; T operator[](uint32_t k) { return get(k); }; }; //=== #line 6 "test/aoj/DSL2E.test.cpp" using namespace std; using llong = long long; struct RAQ { using value_type = long long; using T = value_type; inline static T identity() { return 0; }; inline static T operation(T a, T b) { return a + b; }; }; int main() { llong n, q; llong com; llong s, t, x; llong idx; cin >> n >> q; DualSegmentTree<RAQ> seg(n); for (int i = 0; i < q; i++) { cin >> com; if (com == 0) { cin >> s >> t >> x; s--; seg.update(s, t, x); } else if (com == 1) { cin >> idx; idx--; cout << seg[idx] << '\n'; } } };