#line 1 "a.cpp" #define PROBLEM "" #line 2 "/home/kuhaku/kuhaku/github/atcoder-lib/lib/template/template.hpp" #include using namespace std; template bool chmax(T &a, const U &b) { return a < b ? a = b, true : false; } template bool chmin(T &a, const U &b) { return b < a ? a = 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; const double PI = acos(-1.0); #line 2 "/home/kuhaku/kuhaku/github/atcoder-lib/lib/binary_tree/dynamic_segment_tree.hpp" /** * @brief 動的セグメント木 * * @tparam T * @tparam F */ template struct dynamic_segment_tree { struct Node { Node *parent, *left, *right; T value; Node(Node *ptr) : parent(ptr), left(nullptr), right(nullptr), value() {} }; Node *root; int64_t N; const T e; const F op; dynamic_segment_tree(int64_t _n, T _e, F &&_op) : e(_e), op(_op) { init(_n); } dynamic_segment_tree(int64_t _n, T _e, const F &_op) : e(_e), op(_op) { init(_n); } void init(int64_t n) { for (this->N = 1; N < n; this->N <<= 1) {} this->root = new Node(nullptr); } void update(int64_t k, T x) { assert(0 <= k && k < N); Node *node = this->root; int64_t l = 0, r = this->N; while (r - l > 1) { int64_t m = (l + r) >> 1; if (k < m) { if (!node->left) node->left = new Node(node); node = node->left; r = m; } else { if (!node->right) node->right = new Node(node); node = node->right; l = m; } } node->value = x; while (node->parent) { node = node->parent; node->value = op(node->left ? node->left->value : e, node->right ? node->right->value : e); } } T query() const { return this->root->value; } T query(int64_t a, int64_t b) const { assert(0 <= a && a <= N); assert(0 <= b && b <= N); return this->query(a, b, this->root, 0, this->N); } T query(int64_t a, int64_t b, Node *node, int64_t l, int64_t r) const { if (a <= l && r <= b) return node->value; if (r <= a || b <= l) return e; return op(node->left ? this->query(a, b, node->left, l, (l + r) >> 1) : e, node->right ? this->query(a, b, node->right, (l + r) >> 1, r) : e); } }; #line 3 "/home/kuhaku/kuhaku/github/atcoder-lib/lib/template/atcoder.hpp" using ll = int64_t; using ld = long double; #define FOR(i, m, n) for(int i = (m); i < (n); ++i) #define FORR(i, m, n) for(int i = (m)-1; i >= (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() template istream &operator>>(istream &is, vector &v) { for (T &i : v) is>>i; return is; } template ostream &operator<<(ostream &os, const 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) cout<(tail)...); } template void ce(Head&& head, Tail&&... tail) { if constexpr(sizeof...(tail)==0) cerr<(tail)...); } template auto make_vector(T x, int arg, Args ...args) { if constexpr(sizeof...(args)==0) return vector(arg, x); else return vector(arg,make_vector(x, args...)); } void sonic() { ios::sync_with_stdio(false); cin.tie(nullptr); } void setp(const int n) { cout << fixed << setprecision(n); } #line 4 "a.cpp" int main(void) { sonic(); setp(10); auto op = [](auto a, auto b) { return a + b; }; dynamic_segment_tree st(1e9, 0L, op); int n; cin >> n; ll ans = 0; unordered_map mp; rep(i, n) { int a, b, c; cin >> a >> b >> c; if (!a) { st.update(b, mp[b] + c); mp[b] += c; } else { ans += st.query(b, c + 1); } } co(ans); return 0; }