#include #pragma GCC diagnostic ignored "-Wsign-compare" #pragma GCC diagnostic ignored "-Wsign-conversion" //!===========================================================!// //! 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; using ull = unsigned long long; std::mt19937 mt{std::random_device{}()}; template constexpr T INF = std::numeric_limits::max() / 4; template constexpr T MOD = static_cast(1000000007); 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::priority_queue& v) { auto q = v; os << "["; while (not q.empty()) { os << q.top() << ",", q.pop(); } return os << "]\n"; } template std::ostream& operator<<(std::ostream& os, const std::queue& v) { auto q = v; os << "["; while (not q.empty()) { os << q.front() << ",", q.pop(); } return os << "]\n"; } 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::stack& v) { auto q = v; os << "["; while (not q.empty()) { os << q.top() << ",", q.pop(); } return os << "]\n"; } 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(...) (std::cerr << "(" << #__VA_ARGS__ << ") = ("), HogeHogeSansuu(__VA_ARGS__), std::cerr << ")" << std::endl; void HogeHogeSansuu() { ; } template void HogeHogeSansuu(const T x) { std::cerr << x; } template void HogeHogeSansuu(const T x, Args... args) { (std::cerr << x << ", "), HogeHogeSansuu(args...); } template std::vector Vec(const std::size_t n, T v) { return std::vector(n, v); } template auto Vec(const std::size_t n, Args... args) { return std::vector(n, Vec(args...)); } template constexpr T PopCount(T v) { return v = (v & 0x5555555555555555ULL) + (v >> 1 & 0x5555555555555555ULL), v = (v & 0x3333333333333333ULL) + (v >> 2 & 0x3333333333333333ULL), v = (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL, static_cast(v * 0x0101010101010101ULL >> 56 & 0x7f); } template constexpr T log2p1(T v) { return v |= (v >> 1), v |= (v >> 2), v |= (v >> 4), v |= (v >> 8), v |= (v >> 16), v |= (v >> 32), PopCount(v); } template constexpr bool ispow2(const T v) { return (v << 1) == (T(1) << (log2p1(v))); } template constexpr T ceil2(const T v) { return ispow2(v) ? v : T(1) << log2p1(v); } template constexpr T floor2(const T v) { return v == 0 ? T(0) : ispow2(v) ? v : T(1) << (log2p1(v) - 1); } //!====================================================================================================!// //! 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 Ind SUP = (Ind)1 << SUPBIT; 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 Ind a) { return accumulate(a, a + 1); } void set(Ind 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), this->up(p); } }; rec(rec, root, 0, SUP); } T accumulate(const Ind L, const Ind R) { auto rec = [&](auto&& self, Ptr p, const Ind l, const Ind r) -> T { if (L <= l and r <= R) { return p->V; } else if (r <= L or R <= l) { return ValMonoid::id(); } else { if (l == L and r == R) { return p->V; } if (not p->left) { p->bear(); } const Ind 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, std::min(R, r) - std::max(l, L)); } }; return rec(rec, root, 0, SUP); } void modify(const Ind L, const Ind R, const F& f) { auto rec = [&](auto&& self, Ptr p, const Ind l, const Ind r) -> void { if (L <= l and r <= R) { this->update(p, f, r - l); } else if (r <= L or R <= l) { } else { if (not p->left) { p->bear(); } const std::size_t mid = (l + r) / 2; this->update(p->left, p->A, mid - l), this->update(p->right, p->A, r - mid); self(self, p->left, l, mid), self(self, p->right, mid, r); this->up(p), p->A = OpMonoid::id(); } }; rec(rec, root, 0, SUP); } 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, const Ind l) { p->V = act(f, p->V, l), 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' !// //!==========================================================================!// namespace for_dynamic { // これ本当にやめたい template struct Sum_Plus { using VT = VX; struct ValMonoid { VT operator()(const VT& a, const VT& b) const { return a + b; } static constexpr VT id() { return 0; } }; using OT = OX; struct OpMonoid { OT operator()(const OT& f1, const OT& f2) const { return f1 + f2; } static constexpr OT id() { return 0; } }; template VT operator()(const OT& f, const VT& x, const Ind l) const { return x + (VT)l * f; } }; } // namespace for_dynamic int main() { DynamicLazySeg, 30> dseg; std::cin.tie(nullptr); std::ios::sync_with_stdio(false); 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, y; std::cin >> x >> y; const auto p = dseg.get(x); dseg.set(x, p + y); } else { int l, r; std::cin >> l >> r, r++; ans += dseg.accumulate(l, r); } } std::cout << ans << std::endl; return 0; }