#include //!===========================================================!// //! dP dP dP !// //! 88 88 88 !// //! 88aaaaa88a .d8888b. .d8888b. .d888b88 .d8888b. 88d888b. !// //! 88 88 88ooood8 88' `88 88' `88 88ooood8 88' `88 !// //! 88 88 88. ... 88. .88 88. .88 88. ... 88 !// //! dP dP `88888P' `88888P8 `88888P8 `88888P' dP !// //!===========================================================!// using ld = long double; using ll = long long; std::mt19937 mt{std::random_device{}()}; template constexpr F PI() { return 3.1415926535897932385; } template std::ostream& operator<<(std::ostream& os, const std::array& v) { os << "["; for (const auto& e : v) { os << e << ","; } return (os << "]" << std::endl); } template std::ostream& operator<<(std::ostream& os, const std::deque& v) { os << "["; for (const auto& e : v) { os << e << ","; } return (os << "]" << std::endl); } template std::ostream& operator<<(std::ostream& os, const std::multimap& v) { os << "["; for (const auto& e : v) { os << "<" << e.first << ": " << e.second << ">,"; } return (os << "]" << std::endl); } template std::ostream& operator<<(std::ostream& os, const std::multiset& v) { os << "["; for (const auto& e : v) { os << e << ","; } return (os << "]" << std::endl); } template std::ostream& operator<<(std::ostream& os, const std::map& v) { os << "["; for (const auto& e : v) { os << "<" << e.first << ": " << e.second << ">,"; } return (os << "]" << std::endl); } template std::ostream& operator<<(std::ostream& os, const std::pair& v) { return (os << "<" << v.first << "," << v.second << ">"); } template std::ostream& operator<<(std::ostream& os, const std::set& v) { os << "["; for (const auto& e : v) { os << e << ","; } return (os << "]" << std::endl); } template std::ostream& operator<<(std::ostream& os, const std::unordered_multimap& v) { os << "["; for (const auto& e : v) { os << "<" << e.first << ": " << e.second << ">,"; } return (os << "]" << std::endl); } template std::ostream& operator<<(std::ostream& os, const std::unordered_multiset& v) { os << "["; for (const auto& e : v) { os << e << ","; } return (os << "]" << std::endl); } template std::ostream& operator<<(std::ostream& os, const std::unordered_map& v) { os << "["; for (const auto& e : v) { os << "<" << e.first << ": " << e.second << ">,"; } return (os << "]" << std::endl); } template std::ostream& operator<<(std::ostream& os, const std::unordered_set& v) { os << "["; for (const auto& e : v) { os << e << ","; } return (os << "]" << std::endl); } template std::ostream& operator<<(std::ostream& os, const std::vector& v) { os << "["; for (const auto& e : v) { os << e << ","; } return (os << "]" << std::endl); } #define show(x) std::cerr << #x << " = " << (x) << std::endl //!====================================================================================================!// //! 888888ba dP .d88888b !// //! 88 `8b 88 88. "' !// //! 88 88 dP dP 88d888b. 88 .d8888b. d888888b dP dP `Y88888b. .d8888b. .d8888b. !// //! 88 88 88 88 88' `88 88 88' `88 .d8P' 88 88 `8b 88ooood8 88' `88 !// //! 88 .8P 88. .88 88 88 88 88. .88 .Y8P 88. .88 d8' .8P 88. ... 88. .88 !// //! 8888888P `8888P88 dP dP 88888888P `88888P8 d888888P `8888P88 Y88888P `88888P' `8888P88 !// //! .88 .88 .88 !// //! d8888P d8888P d8888P !// //!====================================================================================================!// template class DynamicLazySeg { public: static constexpr std::size_t INDSUP = 1UL << 30; using BaseAlgebra = Base; using ValMonoid = typename BaseAlgebra::ValMonoid; using OpMonoid = typename BaseAlgebra::OpMonoid; using T = typename BaseAlgebra::VT; using F = typename BaseAlgebra::OT; DynamicLazySeg() : root{std::make_shared()} {} T get(const std::size_t a) const { return accumulate(a, a + 1); } void set(std::size_t a, const T& val) { modify(a, a + 1, OpMonoid::id()); auto rec = [&](auto&& self, const Ptr p, Ind L, Ind R) -> void { if (L == a and R == a + 1) { p->V = val; } else { if (not p->left) { p->bear(); } const Ind M = (L + R) / 2; Ptr next = (a < M ? p->left : p->right); (a < M ? R : L) = M, self(self, next, L, R); up(p); } }; rec(rec, root, 0, INDSUP); } T accumulate(const std::size_t L, const std::size_t R) const { auto rec = [&](auto&& self, const Ptr p, const std::size_t l, const std::size_t r) -> T { if (L <= l and r <= R) { return p->V; } else if (r <= L or R <= l) { return ValMonoid::id(); } else { if (not p->left) { return p->V; } const std::size_t mid = (l + r) / 2; const T vl = self(self, p->left, l, mid), vr = self(self, p->right, mid, r), v = acc(vl, vr); return act(p->A, v); } }; return rec(rec, root, 0, INDSUP); } void modify(const std::size_t L, const std::size_t R, const F& f) { auto rec = [&](auto&& self, Ptr p, const std::size_t l, const std::size_t r) -> void { if (L <= l and r <= R) { update(p, f); } else if (r <= L or R <= l) { } else { if (not p->left) { p->bear(); } update(p->left, p->A), this->update(p->right, p->A); const std::size_t mid = (l + r) / 2; self(self, p->left, l, mid), self(self, p->right, mid, r); up(p), p->A = OpMonoid::id(); } }; rec(rec, root, 0, INDSUP); } private: const ValMonoid acc{}; const OpMonoid compose{}; const BaseAlgebra act{}; struct Node { Node() : V{ValMonoid::id()}, A{OpMonoid::id()} {} void bear() { left = std::make_shared(), right = std::make_shared(); } using Ptr = std::shared_ptr; T V; F A; Ptr left, right; }; using Ptr = typename Node::Ptr; void up(Ptr p) { p->V = acc(p->left->V, p->right->V); } void update(Ptr p, const F& f) { p->V = act(f, p->V), p->A = compose(f, p->A); } Ptr root; }; //!==========================================================================!// //! .d88888b 888888ba dP !// //! 88. "' 88 `8b 88 !// //! `Y88888b. dP dP 88d8b.d8b. a88aaaa8P' 88 dP dP .d8888b. !// //! `8b 88 88 88'`88'`88 88888888 88 88 88 88 Y8ooooo. !// //! d8' .8P 88. .88 88 88 88 88 88 88. .88 88 !// //! Y88888P `88888P' dP dP dP dP dP `88888P' `88888P' !// //!==========================================================================!// template struct Sum_Plus { using VT = std::pair; struct ValMonoid { VT operator()(const VT& a, const VT& b) const { return {a.first + b.first, a.second + b.second}; } static constexpr VT id() { return {0, 0}; } }; using OT = OX; struct OpMonoid { OT operator()(const OT& f1, const OT& f2) const { return f1 + f2; } static constexpr OT id() { return 0; } }; VT operator()(const OT& f, const VT& x) const { return {x.first + x.second * f, x.second}; } }; int main() { DynamicLazySeg, 40> dseg; int Q; std::cin >> Q; ll ans = 0; for (int q = 0; q < Q; q++) { int t; std::cin >> t; if (t == 0) { int x; ll y; std::cin >> x >> y; const auto p = dseg.get(x); dseg.set(x, {p.first + y, p.second}); } else { int l, r; std::cin >> l >> r, r++; ans += dseg.accumulate(l, r).first; } } std::cout << ans << std::endl; return 0; }