#line 1 "test.cpp" #define PROBLEM "https://yukicoder.me/problems/no/789" #include using namespace std; #line 7 "/home/hidehic0/src/github.com/hidehic0/library_cpp/templates/alias.hpp" template using VC = std::vector; template using rpriority_queue = std::priority_queue, std::greater>; using ll = long long; using ld = long double; using pii = std::pair; using vi = VC; using vvi = VC; using vvvi = VC; using vb = VC; using vvb = VC; using vf = VC; using vvf = VC; using vpii = VC; using vvpii = VC; using si = std::set; using spii = std::set; using mii = std::map; const std::string upperlist = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; const std::string lowerlist = "abcdefghijklmnopqrstuvwxyz"; #define mp make_pair #define dms << " " << constexpr int MOD998 = 998244353; #line 4 "/home/hidehic0/src/github.com/hidehic0/library_cpp/templates/macro.hpp" // 引数の長さで内容が変わるrep 参考: https://trap.jp/post/1224 #define overload4(a, b, c, d, ...) d #define _rep(i, n) for (int i = 0; i < (int)(n); i++) #define REP(i, a, b) for (int i = (int)(a); i < (int)(b); ++i) #define rep(...) overload4(__VA_ARGS__, REP, _rep)(__VA_ARGS__) #define _rrep(i, n) for (int i = n - 1; i >= 0; i--) #define RREP(i, a, b) for (int i = (int)(b - 1); i >= (int)(a); i--) #define rrep(...) overload4(__VA_ARGS__, RREP, _rrep)(__VA_ARGS__) #define all(a) (a).begin(), (a).end() template bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; } template bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; } template std::istream &operator>>(std::istream &is, std::pair &p) { is >> p.first >> p.second; return is; } template std::istream &operator>>(std::istream &is, std::vector &v) { for (T &in : v) is >> in; return is; } template std::ostream &operator<<(std::ostream &os, const std::vector &v) { for (int i = 0; i < static_cast(v.size()); i++) { os << v[i] << (i + 1 == v.size() ? "" : " "); } return os; } // pythonのprintライクな関数 参考: // https://nyaannyaan.github.io/library/template/inout.hpp inline void out() { std::cout << std::endl; } template void out(const T &t, const U &...u) { std::cout << t; if (sizeof...(u)) std::cout << sep; out(u...); } // cinの短縮関数 参考: https://nyaannyaan.github.io/library/template/inout.hpp inline void in() {} template void in(T &t, U &...u) { std::cin >> t; in(u...); } template inline T ceil_div(T a, T b) { return (a + b - 1) / b; } template inline T mod_pow(T a, T n, T mod) { T res = 1; while (n) { if (n % 2 != 0) { res *= a; res %= mod; } a *= a; a %= mod; n >>= 1; } return res; } template inline T minus_mod(T a, T b) { return ((a % b) + b) % b; } template void apply_vec(std::vector &v, T (*fn)(T)) { for (int i = 0; i < v.size(); i++) v[i] = fn(v[i]); } template struct Top2 { T a, b; Top2() {} Top2(T a) : a(a) {} Top2(T a, T b) : a(a), b(b) {} void add(const T &v) { if (Comp{}(v, a)) b = a, a = v; else if (Comp{}(v, b)) b = v; } friend Top2 operator*(const Top2 &lhs, const Top2 &rhs) { auto n = lhs; n.add(rhs.a), n.add(rhs.b); return n; } Top2 &operator*=(const Top2 &rhs) { (*this) = (*this) * rhs; return *this; } }; template struct TopMin2 : public Top2> { using Top2>::Top2; }; template struct TopMax2 : public Top2> { using Top2>::Top2; }; #line 7 "test.cpp" #line 3 "/home/hidehic0/src/github.com/hidehic0/library_cpp/segtree/dynamic-segtree.hpp" template struct DynamicSegtree { static_assert(std::is_convertible_v>, "op must work as S(S, S)"); static_assert(std::is_convertible_v>, "e must work as S()"); public: long long _n; DynamicSegtree(long long n) : _n(n), root(nullptr) {} void set(long long p, const S &x) { assert(0 <= p && p < _n); set(root, 0, _n, p, x); } std::optional get(long long p) { assert(0 <= p && p < _n); return get(root, 0, _n, p); } S prod(long long l, long long r) { assert(0 <= l && l <= r && r <= _n); return prod(root, 0, _n, l, r); } private: struct Node; using node_ptr = std::unique_ptr; struct Node { S value; node_ptr left, right; Node(S value) : value(value), left(nullptr), right(nullptr) {} }; node_ptr root; void set(node_ptr &node, long long a, long long b, long long p, const S &x) { if (!node) node = std::make_unique(e()); if (b - a == 1) { node->value = x; return; } long long mid = (a + b) >> 1LL; if (p < mid) set(node->left, a, mid, p, x); else set(node->right, mid, b, p, x); node->value = e(); if (node->left) node->value = op(node->value, node->left->value); if (node->right) node->value = op(node->value, node->right->value); } std::optional get(const node_ptr &node, long long a, long long b, long long p) { if (!node) return std::nullopt; if (b - a == 1) return node->value; long long mid = (a + b) >> 1LL; if (p < mid) return get(node->left, a, mid, p); else return get(node->right, mid, b, p); } S prod(const node_ptr &node, long long a, long long b, long long l, long long r) { if (!node || b <= l || r <= a) return e(); if (l <= a && b <= r) return node->value; long long mid = (a + b) >> 1; return op(prod(node->left, a, mid, l, r), prod(node->right, mid, b, l, r)); } }; #line 9 "test.cpp" int main() { ll Q; in(Q); DynamicSegtree seg( 1e9 + 10); ll ans = 0; while (Q--) { ll t; in(t); if (t == 0) { ll x, y; in(x, y); auto t = seg.get(x); if (!t) seg.set(x, y); else seg.set(x, *t + y); } else { ll l, r; in(l, r); ans += seg.prod(l, r + 1); } } out(ans); }