#line 1 "a.cpp" #define PROBLEM "" #line 2 "/home/kuhaku/home/github/algo/lib/template/template.hpp" #pragma GCC target("sse4.2,avx2,bmi2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include using namespace std; template bool chmax(T &a, const U &b) { return a < (T)b ? a = (T)b, true : false; } template bool chmin(T &a, const U &b) { return (T)b < a ? a = (T)b, true : false; } constexpr int64_t INF = 1000000000000000003; constexpr int Inf = 1000000003; constexpr int MOD = 1000000007; constexpr int MOD_N = 998244353; constexpr double EPS = 1e-7; constexpr double PI = M_PI; #line 3 "/home/kuhaku/home/github/algo/lib/math/pow.hpp" std::int64_t pow_int(std::int64_t a, std::int64_t n) { assert(n >= 0); std::int64_t res = 1, mul = a; for (; n > 0; n >>= 1) { if (n & 1) res *= mul; mul *= mul; } return res; } std::int64_t inv_mod(std::int64_t a, std::int64_t mod) { std::int64_t b = mod, u = 1, v = 0, t; while (b > 0) { t = a / b; swap(a -= t * b, b); swap(u -= t * v, v); } return u >= 0 ? u % mod : (mod - (-u) % mod) % mod; } std::int64_t pow_mod(std::int64_t a, std::int64_t n, std::int64_t mod) { if (n < 0) return inv_mod(pow_mod(a, -n, mod), mod); std::int64_t res = 1, mul = a; for (; n > 0; n >>= 1) { if (n & 1) (res *= mul) %= mod; (mul *= mul) %= mod; } return res; } int ceil_pow2(std::int64_t n) { int x = 0; while ((std::uint64_t(1) << x) < (std::uint64_t)(n)) ++x; return x; } #line 2 "/home/kuhaku/home/github/algo/lib/segment_tree/monoid.hpp" template struct Add { using value_type = T; static constexpr T id = T(0); static constexpr T op(const T &lhs, const T &rhs) { return lhs + rhs; } template static constexpr U f(T lhs, U rhs) { return lhs + rhs; } }; template struct And { using value_type = T; static constexpr T id = T(0); static constexpr T op(const T &lhs, const T &rhs) { return lhs & rhs; } template static constexpr U f(T lhs, U rhs) { return lhs & rhs; } }; template struct Or { using value_type = T; static constexpr T id = T(0); static constexpr T op(const T &lhs, const T &rhs) { return lhs | rhs; } template static constexpr U f(T lhs, U rhs) { return lhs | rhs; } }; template struct Xor { using value_type = T; static constexpr T id = T(0); static constexpr T op(const T &lhs, const T &rhs) { return lhs ^ rhs; } template static constexpr U f(T lhs, U rhs) { return lhs ^ rhs; } }; template struct Min { using value_type = T; static constexpr T id = numeric_limits::max(); static constexpr T op(const T &lhs, const T &rhs) { return min(lhs, rhs); } template static constexpr U f(T lhs, U rhs) { return min((U)lhs, rhs); } }; template struct Max { using value_type = T; static constexpr T id = numeric_limits::min(); static constexpr T op(const T &lhs, const T &rhs) { return max(lhs, rhs); } template static constexpr U f(T lhs, U rhs) { return max((U)lhs, rhs); } }; template struct Update { using value_type = T; static constexpr T id = numeric_limits::max(); static constexpr T op(const T &lhs, const T &rhs) { return lhs == Update::id ? rhs : lhs; } template static constexpr U f(T lhs, U rhs) { return lhs == Update::id ? rhs : lhs; } }; #line 4 "/home/kuhaku/home/github/algo/lib/segment_tree/dynamic_segment_tree.hpp" template struct dynamic_segment_tree { private: using T = typename M::value_type; struct _node { using pointer = _node *; pointer parent, left, right; T value; _node(pointer ptr) : parent(ptr), left(nullptr), right(nullptr), value(M::id) {} }; public: using node_ptr = typename _node::pointer; dynamic_segment_tree(std::int64_t n) : root(), _size(), _log() { this->init(n); } T operator[](int k) const { node_ptr node = this->root; for (int i = this->_log - 1; i >= 0; --i) { if (k >> i & 1) { if (!node->right) return M::id; node = node->right; } else { if (!node->left) return M::id; node = node->left; } } return node->value; } T at(int k) const { return this->operator[](k); } T get(int k) const { return this->operator[](k); } void init(std::int64_t n) { this->_log = ceil_pow2(n); this->_size = 1LL << this->_log; this->root = new _node(nullptr); } void set(std::int64_t k, T x) { assert(0 <= k && k < this->_size); node_ptr node = this->root; for (int i = this->_log - 1; i >= 0; --i) { if (k >> i & 1) { if (!node->right) node->right = new _node(node); node = node->right; } else { if (!node->left) node->left = new _node(node); node = node->left; } } node->value = x; while (node->parent) { node = node->parent; node->value = M::op(node->left ? node->left->value : M::id, node->right ? node->right->value : M::id); } } void reset(std::int64_t k) { this->set(k, M::id); } T all_prod() const { return this->root ? this->root->value : M::id; } T prod(int64_t a, int64_t b) const { assert(0 <= a && a <= this->_size); assert(0 <= b && b <= this->_size); return this->prod(a, b, this->root, 0, this->_size); } private: node_ptr root; std::int64_t _size, _log; T prod(int64_t a, int64_t b, node_ptr node, int64_t l, int64_t r) const { if (a <= l && r <= b) return node->value; if (r <= a || b <= l) return M::id; return M::op(node->left ? this->prod(a, b, node->left, l, (l + r) >> 1) : M::id, node->right ? this->prod(a, b, node->right, (l + r) >> 1, r) : M::id); } }; #line 3 "/home/kuhaku/home/github/algo/lib/template/macro.hpp" #define FOR(i, m, n) for (int i = (m); i < int(n); ++i) #define FORR(i, m, n) for (int i = (m)-1; i >= int(n); --i) #define FORL(i, m, n) for (int64_t i = (m); i < int64_t(n); ++i) #define rep(i, n) FOR (i, 0, n) #define repn(i, n) FOR (i, 1, n + 1) #define repr(i, n) FORR (i, n, 0) #define repnr(i, n) FORR (i, n + 1, 1) #define all(s) (s).begin(), (s).end() #line 3 "/home/kuhaku/home/github/algo/lib/template/sonic.hpp" struct Sonic { Sonic() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); } constexpr void operator()() const {} } sonic; #line 5 "/home/kuhaku/home/github/algo/lib/template/atcoder.hpp" using ll = int64_t; using ld = long double; template std::istream &operator>>(std::istream &is, std::pair &p) { return is >> p.first >> p.second; } template std::istream &operator>>(std::istream &is, std::vector &v) { for (T &i : v) is >> i; return is; } template std::ostream &operator<<(std::ostream &os, const std::pair &p) { return os << '(' << p.first << ',' << p.second << ')'; } template std::ostream &operator<<(std::ostream &os, const std::vector &v) { for (auto it = v.begin(); it != v.end(); ++it) { os << (it == v.begin() ? "" : " ") << *it; } return os; } template void co(Head &&head, Tail &&...tail) { if constexpr (sizeof...(tail) == 0) std::cout << head << '\n'; else std::cout << head << ' ', co(std::forward(tail)...); } template void ce(Head &&head, Tail &&...tail) { if constexpr (sizeof...(tail) == 0) std::cerr << head << '\n'; else std::cerr << head << ' ', ce(std::forward(tail)...); } template auto make_vector(T x, int arg, Args... args) { if constexpr (sizeof...(args) == 0) return std::vector(arg, x); else return std::vector(arg, make_vector(x, args...)); } void setp(int n) { std::cout << std::fixed << std::setprecision(n); } void Yes(bool is_correct = true) { std::cout << (is_correct ? "Yes" : "No") << '\n'; } void No(bool is_not_correct = true) { Yes(!is_not_correct); } void YES(bool is_correct = true) { std::cout << (is_correct ? "YES" : "NO") << '\n'; } void NO(bool is_not_correct = true) { YES(!is_not_correct); } void Takahashi(bool is_correct = true) { std::cout << (is_correct ? "Takahashi" : "Aoki") << '\n'; } void Aoki(bool is_not_correct = true) { Takahashi(!is_not_correct); } #line 4 "a.cpp" int main(void) { int n; cin >> n; dynamic_segment_tree> st(Inf); ll ans = 0; rep (i, n) { int a, x, y; cin >> a >> x >> y; if (a == 0) { st.set(x, st[x] + y); } else { ans += st.prod(x, y + 1); } } co(ans); return 0; }