#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 uint = unsigned int; using ll = long long; using ull = unsigned long long; template constexpr T INF = std::numeric_limits::max() / 4; template constexpr T MOD = static_cast(1000000007); template constexpr F PI = static_cast(3.1415926535897932385); //! メルセンヌ・ツイスタ !// std::mt19937 mt{std::random_device{}()}; //! Debug出力 !// #define SHOW(...) (std::cerr << "(" << #__VA_ARGS__ << ") = ("), HogeHogeSansuu(__VA_ARGS__), std::cerr << ")" << std::endl struct has_debugPrint_impl { template static auto check(T&& x) -> decltype(x.debugPrint(), std::true_type{}); template static auto check(...) -> std::false_type; }; template class has_debugPrint : public decltype(has_debugPrint_impl::check(std::declval())) { }; template struct HogeHogeDump { template static void dump(const T& x) { x.debugPrint(); } }; template <> struct HogeHogeDump { template static void dump(const T& x) { std::cerr << x; } }; void HogeHogeSansuu() { ; } template void HogeHogeSansuu(const T& x) { HogeHogeDump::value>::dump(x); } template void HogeHogeSansuu(const T& x, Args... args) { HogeHogeDump::value>::dump(x), std::cerr << ",", HogeHogeSansuu(args...); } //! 自作Assert !// #ifdef HOGEPACHI_ASSERT #define Assert(expr, dump) (not(expr) and (std::cerr << __FILE__ << "(" << __LINE__ << "): Assertion \"" << #expr << "\" failed. [Detail]: ", (dump), exit(1), true)) #else #define Assert(...) void(0) #endif //! chminとchmax !// template bool chmin(T& a, const T& b) { return a = std::min(a, b), a == b; } template bool chmax(T& a, const T& b) { return a = std::max(a, b), a == b; } //! Rep関数 !// template void For(const T s, const T t, const F f) { for (T i = s; i != t; i += T(s < t ? 1 : -1)) { f(i); } } template void Rep(const T N, const F f) { For(0, N, f); } template void RRep(const T N, const F f) { For(N - 1, -1, f); } //! Vec関数 !// 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(const T u) { #ifdef __has_builtin return u == 0 ? T(0) : (T)__builtin_popcountll(u); #else unsigned long long v = static_cast(u); return v = (v & 0x5555555555555555ULL) + (v >> 1 & 0x5555555555555555ULL), v = (v & 0x3333333333333333ULL) + (v >> 2 & 0x3333333333333333ULL), v = (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL, static_cast(v * 0x0101010101010101ULL >> 56 & 0x7f); #endif } template constexpr T log2p1(const T u) { #ifdef __has_builtin return u == 0 ? T(0) : T(64 - __builtin_clzll(u)); #else unsigned long long v = static_cast(u); return v = static_cast(v), v |= (v >> 1), v |= (v >> 2), v |= (v >> 4), v |= (v >> 8), v |= (v >> 16), v |= (v >> 32), popCount(v); #endif } template constexpr T clog(const T v) { return v == 0 ? T(0) : log2p1(v - 1); } template constexpr T msbp1(const T v) { return log2p1(v); } template constexpr T lsbp1(const T v) { #ifdef __has_builtin return __builtin_ffsll(v); #else return v == 0 ? T(0) : popCount((v & (-v)) - T(1)) + T(1); #endif } template constexpr bool ispow2(const T v) { return popCount(v) == 1; } template constexpr T ceil2(const T v) { return v == 0 ? T(1) : T(1) << log2p1(v - 1); } template constexpr T floor2(const T v) { return v == 0 ? T(0) : T(1) << (log2p1(v) - 1); } //! 累積和 !// template struct Accum { template Accum(const InIt first, const InIt last) : accum(std::size_t(std::distance(first, last))) { std::partial_sum(first, last, accum.begin()); } T sum(const std::size_t i) const { return i == 0 ? T(0) : accum[i - 1]; } T sum(const std::size_t l, const std::size_t r) const { return sum(r) - sum(l); } std::vector accum; }; template struct Accum2D { Accum2D(const std::vector>& t) : accum{t} { for (std::size_t i = 0; i < accum.size(); i++) { for (std::size_t j = 1; j < accum[i].size(); j++) { accum[i][j] += accum[i][j - 1]; } } for (std::size_t i = 1; i < accum.size(); i++) { for (std::size_t j = 0; j < accum[i].size(); j++) { accum[i][j] += accum[i - 1][j]; } } } T sum(const std::size_t y, const std::size_t x) const { return y == 0 or x == 0 ? T(0) : accum[y - 1][x - 1]; } T sum(const std::size_t ymin, const std::size_t ysup, const std::size_t xmin, const std::size_t xsup) const { return sum(ysup, xsup) - sum(ymin, xmin); } std::vector> accum; }; //! 座標圧縮 !// template struct Zip { template Zip(const InIt first, const InIt last) : unzip(std::size_t(std::distance(first, last))) { std::copy(first, last, unzip), std::sort(unzip.begin(), unzip.end()), unzip.erase(std::unique(unzip.begin(), unzip.end()), unzip.end()); for (std::size_t i = 0; i < unzip.size(); i++) { zip[unzip[i]] = i; } } std::vector unzip; std::map zip; }; //! STLの出力関数 !// 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); } //!=============================================================================!// //! 888888ba .d88888b d888888P !// //! 88 '8b 88. "' 88 !// //! 88 88 'Y88888b. .d8888b. .d8888b. 88 88d888b. .d8888b. .d8888b. !// //! 88 88 '8b 88ooood8 88' '88 88 88' '88 88ooood8 88ooood8 !// //! 88 .8P d8' .8P 88. ... 88. .88 88 88 88. ... 88. ... !// //! 8888888P Y88888P '88888P' '8888P88 dP dP '88888P' '88888P' !// //! .88 !// //! d8888P !// //!=============================================================================!// template class DSegTree { public: DSegTree() {} static constexpr Ind SUP = (Ind)1 << B; using T = typename Monoid::T; T get(const Ind a) const { return fold(a, a + 1); } void set(const Ind a, const T& val) { root = update(root, a, val, 0, SUP); } T fold(const Ind L, const Ind R) const { auto dfs = [&](auto&& self, const Ptr p, const Ind l, const Ind r, const Ind inf, const Ind sup) -> T { if (p == nullptr or sup <= l or r <= inf) { return Monoid::id(); } if (l <= inf and sup <= r) { return p->V; } const Ind leaf = p->leaf, mid = (inf + sup) >> 1; return (l <= leaf and leaf < r ? acc(self(self, p->left, l, r, inf, mid), acc(p->LV, self(self, p->right, l, r, mid, sup))) : acc(self(self, p->left, l, r, inf, mid), self(self, p->right, l, r, mid, sup))); }; return dfs(dfs, root, L, R, 0, SUP); } private: const Monoid acc{}; struct Node { Node() : V{Monoid::id()} {} Node(const Ind l, const T& v, const T& lv) : leaf(l), V(v), LV(lv) {} Ind leaf; T V, LV; Node *left = nullptr, *right = nullptr; }; using Ptr = Node*; static T value(const Ptr p) { return p ? p->V : Monoid::id(); } static Node* alloc(const Ind l, const T& v, const T& lv) { static std::size_t head = 0; static Node buffer[POOL]; Assert(head < POOL, std::cerr << "head(" << head << ") >= POOL(" << POOL << ")\n"); return buffer[head++] = Node(l, v, lv), buffer + head - 1; } static Node* update(Ptr p, Ind a, T v, const Ind inf, const Ind sup) { static Monoid acc; if (p == nullptr) { return alloc(a, v, v); } const Ind l = p->leaf, mid = (inf + sup) >> 1; if (l == a) { return p->LV = v, p->V = acc(value(p->left), acc(p->LV, value(p->right))), p; } else if (a < mid) { if (l < a) { std::swap(p->leaf, a), std::swap(p->LV, v); } p->left = update(p->left, a, v, inf, mid); } else { if (l > a) { std::swap(p->leaf, a), std::swap(p->LV, v); } p->right = update(p->right, a, v, mid, sup); } return p->V = acc(value(p->left), acc(p->LV, value(p->right))), p; } Ptr root = nullptr; }; //!=================================!// //! .d88888b !// //! 88. "' !// //! 'Y88888b. dP dP 88d8b.d8b. !// //! '8b 88 88 88''88''88 !// //! d8' .8P 88. .88 88 88 88 !// //! Y88888P '88888P' dP dP dP !// //!=================================!// template struct Sum { using T = X; T operator()(const T& a, const T& b) const { return a + b; } static constexpr T id() { return T{}; } }; int main() { std::cin.tie(nullptr); std::ios::sync_with_stdio(false); DSegTree> 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, 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.fold(l, r); } } std::cout << ans << std::endl; return 0; }