// #define PROBLEM "https://yukicoder.me/problems/no/789" // // #include // // #include "../../algebra/monoid/monoid_plus.hpp" // #include "../../segment_tree/dynamic_segment_tree.hpp" // // int main() { // int n; // std::cin >> n; // const int m = 1000000001; // // Q log_2(N) = n log_2(m) = 3000000 くらい // DynamicSegmentTree, 3000000> seg_add(m); // // DynamicSegmentTree, 3000000> seg_set(m); // long long ans = 0; // for (int i = 0; i < n; i++) { // int type; // std::cin >> type; // if (type == 0) { // int x, y; // std::cin >> x >> y; // seg_add.add(x, y); // // seg_set.set(x, seg_set.get(x) + y); // } else { // int l, r; // std::cin >> l >> r; // r++; // // assert(seg_add.prod(l, r) == seg_set.prod(l, r)); // ans += seg_add.prod(l, r); // } // } // std::cout << ans << '\n'; // return 0; // } #define PROBLEM "https://yukicoder.me/problems/no/789" #include template struct MonoidPlus { using value_type = T; static constexpr T operation(const T& a, const T& b) noexcept { return a + b; } static constexpr T identity() noexcept { return T(0); } static constexpr T inverse(const T& a) noexcept { return -a; } static constexpr bool commutative = true; }; #include #include // Dynamic Segment Tree // Q log_2(N) は Q = 500000, N = 10^18 のとき 30000000 くらい template struct DynamicSegmentTree { public: using S = typename MS::value_type; struct Node { S d; Node *l, *r; Node() = default; Node(S v, Node* l = nullptr, Node* r = nullptr) : d(v), l(l), r(r) {} }; DynamicSegmentTree() = default; explicit DynamicSegmentTree(int n) : n(n), root(nullptr) {} void set(int p, const S& x) { assert(0 <= p and p < n); set(p, x, 0, n, root); } void add(int p, const S& x) { assert(0 <= p and p < n); add(p, x, 0, n, root); } S operator[](int p) const { assert(0 <= p and p < n); return prod(p, p + 1); } S get(int p) const { assert(0 <= p and p < n); return prod(p, p + 1); } S prod(int l, int r) const { assert(0 <= l and l <= r and r <= n); return prod(l, r, 0, n, root); } S all_prod() const { return root->d; } private: int n; Node* root; static inline Node pool[MAX_NODES]; static inline int pool_idx = 0; Node* new_node(S v, Node* l = nullptr, Node* r = nullptr) { return &(pool[pool_idx++] = Node(v, l, r)); } S merge(Node* l, Node* r) { return MS::operation((l == nullptr ? MS::identity() : l->d), (r == nullptr ? MS::identity() : r->d)); } Node* set(int p, const S& x, int l, int r, Node*& np) { if (np == nullptr) { np = new_node(MS::identity()); } if (l + 1 == r) { np->d = x; return np; } int m = (l + r) / 2; if (l <= p and p < m) { np->d = merge(set(p, x, l, m, np->l), np->r); } else { np->d = merge(np->l, set(p, x, m, r, np->r)); } return np; } Node* add(int p, const S& x, int l, int r, Node*& np) { if (np == nullptr) { np = new_node(MS::identity()); } if (l + 1 == r) { np->d = MS::operation(np->d, x); return np; } int m = (l + r) / 2; if (l <= p and p < m) { np->d = merge(add(p, x, l, m, np->l), np->r); } else { np->d = merge(np->l, add(p, x, m, r, np->r)); } return np; } S prod(int ql, int qr, int l, int r, Node* np) const { if (np == nullptr) return MS::identity(); // [ql, qr) と [l, r) が交差しない if (qr <= l or r <= ql) return MS::identity(); // [ql, qr) が [l, r) を完全に含んでいる if (ql <= l and r <= qr) return np->d; int m = (l + r) / 2; return MS::operation(prod(ql, qr, l, m, np->l), prod(ql, qr, m, r, np->r)); } }; int main() { int n; std::cin >> n; const int m = 1000000001; // Q log_2(N) = n log_2(m) = 3000000 くらい DynamicSegmentTree, 3000000> seg_add(m); // DynamicSegmentTree, 3000000> seg_set(m); long long ans = 0; for (int i = 0; i < n; i++) { int type; std::cin >> type; if (type == 0) { int x, y; std::cin >> x >> y; seg_add.add(x, y); // seg_set.set(x, seg_set.get(x) + y); } else { int l, r; std::cin >> l >> r; r++; // assert(seg_add.prod(l, r) == seg_set.prod(l, r)); ans += seg_add.prod(l, r); } } std::cout << ans << '\n'; return 0; }