#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #if __cplusplus >= 202002L #include #else #define countl_zero __builtin_clzll #endif using namespace std; using lint = long long; using P = pair; using Pii = pair; using ull = unsigned long long; struct FastIO { FastIO() { ios::sync_with_stdio(false); cin.tie(nullptr); cout << fixed << setprecision(12); } } aaaAAAaaaAAA; #define TYPE(n) remove_cvref_t #define rep(i, n) for (TYPE(n) i = 0; i < (n); ++i) #define repe(i, n) for (TYPE(n) i = 0; i <= (n); ++i) #define rep1(i, n) for (TYPE(n) i = 1; i < (n); ++i) #define rep1e(i, n) for (TYPE(n) i = 1; i <= (n); ++i) #define repn(i, a, b) for (TYPE(a) i = (a); i < (b); ++i) #define repne(i, a, b) for (TYPE(a) i = (a); i <= (b); ++i) #define rrep(i, n) for (TYPE(n) i = (n); i >= 0; --i) #define all(vec) begin(vec), end(vec) #define rall(vec) rbegin(vec), rend(vec) constexpr long long Mod = /** 1000'000'007LL /*/ 998244353LL /**/; constexpr long long Inf = 2'000'000'000'000'000'010LL; constexpr int IntInf = 1000'000'010; constexpr double Pi = 3.141592653589793238; constexpr double InvPi = 0.318309886183790671; const int di[] = {0, 1, 0, -1, 0}, dj[] = {1, 0, -1, 0, 0}; #if __has_include() #include using namespace atcoder; using mint = static_modint; template inline istream &operator>>(istream &is, static_modint &rhs) { long long tmp; is >> tmp; rhs = tmp; return is; } template inline istream &operator>>(istream &is, dynamic_modint &rhs) { long long tmp; is >> tmp; rhs = tmp; return is; } template inline ostream &operator<<(ostream &os, const static_modint &rhs) { return os << rhs.val(); } template inline ostream &operator<<(ostream &os, const dynamic_modint &rhs) { return os << rhs.val(); } mint lagrange_interpolation(const vector &y, mint t) { const int n = (int)y.size(); mint res = 0; vector inv(n), fact_inv(n); inv[1] = 1; fact_inv[0] = 1; fact_inv[1] = 1; for (int i = 2; i < n; ++i) { inv[i] = -Mod / i * inv[Mod % i]; fact_inv[i] = fact_inv[i - 1] * inv[i]; } vector prod2(n); prod2.back() = 1; for (int i = n - 1; i > 0; --i) { prod2[i - 1] = (t - i) * prod2[i]; } mint prod1 = 1; for (int i = 0; i < n; ++i) { mint a = y[i]; a *= fact_inv[i] * fact_inv[n - 1 - i]; if ((n - 1 - i) & 1) a = -a; res += a * prod1 * prod2[i]; prod1 *= (t - i); } return res; } template lint inversion_number(const vector vec) { vector v = vec; sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); const int n = vec.size(); lint res = 0; fenwick_tree b(n); for (int i = 0; i < n; ++i) { const int j = lower_bound(v.begin(), v.end(), vec[i]) - v.begin(); res += b.sum(j + 1, n); b.add(j, 1); } return res; } #endif template using prique = priority_queue; template using prique_inv = priority_queue, greater>; template inline istream &operator>>(istream &is, vector &v) { for (auto &&e : v) is >> e; return is; } template inline istream &operator>>(istream &is, complex &c) { double real, imag; is >> real >> imag; c.real(real); c.imag(imag); return is; } template inline ostream &operator<<(ostream &os, const vector &v) { for (auto itr = v.begin(), end_itr = v.end(); itr != end_itr;) { os << *itr; if (++itr != end_itr) os << " "; } return os; } template inline bool chmin(T &a, const U b) { return a > b ? a = b, true : false; } template inline bool chmax(T &a, const U b) { return a < b ? a = b, true : false; } template inline istream &operator>>(istream &is, pair &rhs) { return is >> rhs.first >> rhs.second; } template inline ostream &operator<<(ostream &os, const pair &rhs) { return os << "{" << rhs.first << ", " << rhs.second << "}"; } template inline int getid(const vector &v, const U &value, Pr pred) { return lower_bound(v.begin(), v.end(), value, pred) - v.begin(); } template inline int getid(const vector &v, const U &value) { return getid(v, value, less<>{}); } template T gcd(const vector &vec) { T res = vec.front(); for (T e : vec) { res = gcd(res, e); if (res == 1) return 1; } return res; } template T gcd(initializer_list init) { auto first = init.begin(), last = init.end(); T res = *(first++); for (auto itr = first; itr != last; ++itr) { res = gcd(res, *itr); if (res == 1) return 1; } return res; } template T lcm(const vector &vec) { T res = vec.front(); for (T e : vec) res = lcm(res, e); return res; } template T lcm(initializer_list init) { auto first = init.begin(), last = init.end(); T res = *(first++); for (auto itr = first; itr != last; ++itr) { res = lcm(res, *itr); } return res; } inline void YesNo(bool b) { printf(b ? "Yes\n" : "No\n"); } inline void YESNO(bool b) { printf(b ? "YES\n" : "NO\n"); } inline void takaao(bool b) { printf(b ? "Takahashi\n" : "Aoki\n"); } inline void aotaka(bool b) { printf(b ? "Aoki\n" : "Takahashi\n"); } template void out(T &&t) { cout << t << "\n"; } template void out(Head &&head, Args &&...args) { cout << head << " "; out(forward(args)...); } template T rand(T l, T r) { static mt19937 mt(random_device{}()); if constexpr (is_integral_v) { uniform_int_distribution dist(l, r); return dist(mt); } else if constexpr (is_floating_point_v) { uniform_real_distribution dist(l, r); return dist(mt); } } bool is_prime(lint x) { for (lint i = 2; i * i <= x; ++i) { if (x % i == 0) return false; } return 1 < x; } vector divisors(lint n) { vector f, l; for (lint x = 1; x * x <= n; ++x) { if (n % x == 0) { f.push_back(x); if (x * x != n) l.push_back(n / x); } } f.reserve(f.size() + l.size()); copy(l.rbegin(), l.rend(), back_inserter(f)); return f; } lint phi(lint n) { lint r = n; for (lint i = 2; i * i <= n; ++i) { if (n % i == 0) { r -= r / i; while (n % i == 0) n /= i; } } if (n > 1) r -= r / n; return r; } lint floor_sqrt(lint n) { if (n == 0 || n == 1) return n; lint x0 = 1LL << ((65 - countl_zero(static_cast(n))) >> 1); lint x1 = (x0 + n / x0) >> 1; while (x1 < x0) { x0 = x1; x1 = (x0 + n / x0) >> 1; } return x0; } lint ceil_sqrt(lint n) { const lint f = floor_sqrt(n); if (f * f == n) return f; return f + 1; } template constexpr bool is_intersect(T l1, T r1, T l2, T r2) { return l1 <= r2 && l2 <= r1; } lint modinv(lint a, lint m = Mod) { lint b = m, u = 1, v = 0; while (b != 0) { lint t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } u %= m; if (u < 0) u += m; return u; } lint modpow(lint x, lint n, lint m = Mod) { if (m == 1) return 0; lint res = 1; x %= m; while (n > 0) { if (n & 1) res = res * x % m; x = x * x % m; n >>= 1; } return res; } lint intpow(lint x, lint n) { lint res = 1; while (n > 0) { if (n & 1) res *= x; x *= x; n >>= 1; } return res; } template vector enumerate_fact(int n) { vector fact(n + 1); fact[0] = 1; for (int i = 1; i <= n; ++i) fact[i] = i * fact[i - 1]; return fact; } template > vector enumerate_inv(int n) { vector inv(n + 1); inv[1] = 1; for (int i = 2; i <= n; ++i) inv[i] = MOD - MOD / i * inv[MOD % i]; return inv; } template > vector enumerate_factinv(int n, vector inv) { vector fact_inv(n + 1); fact_inv[0] = 1; for (int i = 1; i <= n; ++i) fact_inv[i] = fact_inv[i - 1] * inv[i]; return fact_inv; } template > vector enumerate_factinv(int n) { return enumerate_factinv(n, enumerate_inv(n)); } template struct Binomial { using T = static_modint; vector fact, inv, fact_inv; explicit Binomial() = default; void build(int n) { fact = enumerate_fact(n); inv = enumerate_inv(n); fact_inv = enumerate_factinv(n, inv); } T comb(int n, int r) const { if (n < 0 || r < 0 || n < r) return 0; if (r == 0 || r == n) return 1; return fact[n] * fact_inv[n - r] * fact_inv[r]; } T perm(int n, int r) const { if (n < 0 || r < 0 || n < r) return 0; return fact[n] * fact_inv[n - r]; } T multi(int n, int r) const { if (n == 0 && r == 0) return 1; if (n < 0 || r < 0) return 0; return r == 0 ? 1 : comb(n + r - 1, r); } }; Binomial binomial; inline mint fact(int n) { return binomial.fact[n]; } inline mint comb(int n, int r) { return binomial.comb(n, r); } inline mint perm(int n, int r) { return binomial.perm(n, r); } inline mint multi(int n, int r) { return binomial.multi(n, r); } template vector uniqued(vector v) { sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); return v; } template vector compressed_index(vector v) { const int n = v.size(); const vector c = uniqued(v); vector res(n); for (int i = 0; i < n; ++i) { res[i] = lower_bound(c.begin(), c.end(), v[i]) - c.begin(); } return res; } // { value, count } template pair, vector> compressed_pair(vector v) { size_t n = v.size(); sort(v.begin(), v.end()); vector cnt, val; cnt.reserve(n); val.reserve(n); int now_cnt = 1; for (size_t i = 1; i < n; ++i) { if (v[i - 1] != v[i]) { cnt.push_back(now_cnt); val.push_back(v[i - 1]); now_cnt = 1; } else ++now_cnt; } cnt.push_back(now_cnt); val.push_back(v.back()); return {val, cnt}; } class Factring { private: const int max_n; vector sieve; public: explicit Factring(int max_n) : max_n(max_n), sieve(max_n + 1) { iota(sieve.begin(), sieve.end(), 0); for (int i = 2; i * i <= max_n; ++i) { if (sieve[i] < i) continue; for (int j = i * i; j <= max_n; j += i) { if (sieve[j] == j) sieve[j] = i; } } } unordered_map calc(int x) const { unordered_map res; while (x > 1) { ++res[sieve[x]]; x /= sieve[x]; } return res; } }; struct UnionFind { int n; vector par, rank, siz, es; // [root(i)] int c; UnionFind() = default; explicit UnionFind(int _n) : n(_n), par(_n), rank(_n), siz(_n, 1), es(_n), c(_n) { iota(par.begin(), par.end(), 0); } int root(int x) { while (par[x] != x) x = par[x] = par[par[x]]; return x; } bool same(int x, int y) { return root(x) == root(y); } void unite(int x, int y) { if (x == y) return; x = root(x); y = root(y); if (x == y) ++es[x]; else { c--; if (rank[x] < rank[y]) { par[x] = y; siz[y] += siz[x]; es[y] += es[x] + 1; } else { par[y] = x; if (rank[x] == rank[y]) ++rank[x]; siz[x] += siz[y]; es[x] += es[y] + 1; } } } int size(int x) { return siz[root(x)]; } vector roots() { vector res; res.reserve(c); for (int i = 0; i < n; ++i) { if (par[i] == i) { res.push_back(i); } } return res; } vector> groups() { vector> res(n); for (int i = 0; i < n; ++i) if (par[i] == i) res[i].reserve(siz[i]); for (int i = 0; i < n; ++i) res[root(i)].push_back(i); res.erase(remove_if(res.begin(), res.end(), [](const vector &v) { return v.empty(); }), res.end()); return res; } }; template class CumulativeSum2D { private: vector> dat; public: CumulativeSum2D() = default; explicit CumulativeSum2D(size_t n) : dat(n + 1, vector(n + 1)) {} CumulativeSum2D(size_t h, size_t w) : dat(h + 1, vector(w + 1)) {} CumulativeSum2D(const vector> &vec) { const size_t h = vec.size(), w = vec.front().size(); dat.resize(h + 1, vector(w + 1)); for (size_t i = 0; i < h; ++i) { for (size_t j = 0; j < w; ++j) { dat[i + 1][j + 1] = dat[i][j + 1] + dat[i + 1][j] - dat[i][j] + vec[i][j]; } } } void add(int h, int w, int v) { dat[h + 1][w + 1] += v; } void build() { const size_t h = dat.size() - 1, w = dat.front().size() - 1; for (size_t i = 0; i < h; ++i) { for (size_t j = 0; j < w; ++j) { dat[i + 1][j + 1] = dat[i][j + 1] + dat[i + 1][j] - dat[i][j]; } } } // [0, h) x [0, w) T sum(int h, int w) const { return sum(0, 0, h, w); } // [h1, h2) x [w1, w2) T sum(int h1, int w1, int h2, int w2) const { return dat[h2][w2] - dat[h1][w2] - dat[h2][w1] + dat[h1][w1]; } }; template class BinaryIndexedTree { private: int n; vector dat; public: BinaryIndexedTree() = default; explicit BinaryIndexedTree(const int size) : n(size), dat(size + 1) {} explicit BinaryIndexedTree(const vector &vec) : n(vec.size()), dat(n + 1) { for (int i = 0; i < n; ++i) dat[i + 1] = vec[i]; for (int i = 1; i <= n; ++i) { const int j = i + (i & -i); if (j <= n) dat[j] += dat[i]; } } // 0-indexed void add(const int a, const T v) { for (int x = a + 1; x <= n; x += (x & -x)) dat[x] += v; } // 0-indexed void set(const int a, const T v) { add(a, v - get(a)); } void reset() { fill(dat.begin(), dat.end(), T(0)); } // [0, a) T sum(const int a) const { T res = 0; for (int x = a; x > 0; x -= (x & -x)) res += dat[x]; return res; } // [a, b) T sum(const int a, const int b) const { return sum(b) - sum(a); } T get(const int i) const { return sum(i, i + 1); } // min i s.t. sum(i) >= w int lower_bound(T w) const { int x = 0, r = 1; while (r < n) r <<= 1; for (int i = r; i > 0; i >>= 1) { if (x + i <= n && dat[x + i] < w) { w -= dat[x + i]; x += i; } } return x + 1; } // min i s.t. sum(i) > w int upper_bound(T w) const { int x = 0, r = 1; while (r < n) r <<= 1; for (int i = r; i > 0; i >>= 1) { if (x + i <= n && dat[x + i] <= w) { w -= dat[x + i]; x += i; } } return x + 1; } }; template T nearest_value(const vector &v, const U &value) { auto itr = lower_bound(v.begin(), v.end(), value); if (itr == v.begin()) return *itr; if (itr == v.end()) return *prev(itr); return min(*itr - value, value - *prev(itr)) + value; } 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: DynamicSegtree(int n_) : n(n_), root(nullptr) {} ~DynamicSegtree() { del(root); } void set(int p, S x) { set(root, 0, n, p, x); } S get(int p) { return get(root, 0, n, p); } S prod(int l, int r) { return prod(root, 0, n, l, r); } private: struct Node; using Node_t = Node *; struct Node { S val; Node_t l, r; Node(S v) : val(v), l(nullptr), r(nullptr) {} }; S get(Node_t t) { return (t == nullptr ? e() : t->val); } int n; Node_t root; void set(Node_t &t, int l, int r, int p, S x) { if (t == nullptr) t = new Node(e()); if (l + 1 == r) { t->val = x; return; } int m = (l + r) >> 1; // [l, m) [m, r) if (p < m) set(t->l, l, m, p, x); else set(t->r, m, r, p, x); t->val = op(get(t->l), get(t->r)); } S get(Node_t t, int l, int r, int p) { if (t == nullptr) return e(); if (l + 1 == r) return t->val; int m = (l + r) >> 1; if (p < m) return get(t->l, l, m, p); return get(t->r, m, r, p); } // query: [l, r), now: [a, b) S prod(Node_t t, int a, int b, int l, int r) { if (t == nullptr || b <= l || r <= a) return e(); if (l <= a && b <= r) return t->val; int c = (a + b) >> 1; return op(prod(t->l, a, c, l, r), prod(t->r, c, b, l, r)); } void del(Node_t &t) { if (t == nullptr) return; del(t->l); del(t->r); delete t; } }; lint op(lint a, lint b) { return a + b; } lint e() { return 0; } int main() { int q; cin >> q; DynamicSegtree seg(1000'000'000 + 1); lint ans = 0; while (q--) { int a, b, c; cin >> a >> b >> c; if (a == 0) seg.set(b, seg.get(b) + c); else ans += seg.prod(b, c + 1); } cout << ans << endl; }