#include #include #include template struct sparse_segment_tree{ private: struct node{ int lx, rx; node *l, *r; Val sum; node(int lx, int rx, Val val): lx(lx), rx(rx), l(nullptr), r(nullptr), sum(val){} }; node *make_node(int lx, int rx, Val val = monoid::template id()){ return new node(lx, rx, val); } Val set(node *v, int k, Val x){ if(v->rx - v->lx == 1) return v->sum = x; int mid = ((long long)v->lx + v->rx) >> 1; if(mid <= k){ if(!v->r) v->r = make_node(mid, v->rx); if(!v->l) return v->sum = set(v->r, k, x); else return v->sum = monoid::template merge(v->l->sum, set(v->r, k, x)); }else{ if(!v->l) v->l = make_node(v->lx, mid); if(!v->r) return v->sum = set(v->l, k, x); else return v->sum = monoid::template merge(set(v->l, k, x), v->r->sum); } } Val get(node *v, int k){ if(!v) return monoid::template id(); if(v->rx - v->lx == 1) return v->sum; int mid = ((long long)v->lx + v->rx) >> 1; if(mid <= k) return get(v->r, k); else return get(v->l, k); } Val update(node *v, int k, Val x){ if(v->rx - v->lx == 1) return v->sum = monoid::template merge(v->sum, x); int mid = ((long long)v->lx + v->rx) >> 1; if(mid <= k){ if(!v->r) v->r = make_node(mid, v->rx); if(!v->l) return v->sum = update(v->r, k, x); else return v->sum = monoid::template merge(v->l->sum, update(v->r, k, x)); }else{ if(!v->l) v->l = make_node(v->lx, mid); if(!v->r) return v->sum = update(v->l, k, x); else return v->sum = monoid::template merge(update(v->l, k, x), v->r->sum); } } Val query(node *v, int l, int r){ if(!v || r <= v->lx || v->rx <= l) return monoid::template id(); if(l <= v->lx && v->rx <= r) return v->sum; return monoid::template merge(query(v->l, l, r), query(v->r, l, r)); } template std::pair bisect_from_left(node *v, const int l, const F &f, Val ok){ if(v->rx <= l) return {-1, ok}; if(l <= v->lx){ Val m = monoid::template merge(ok, v->sum); if(!f(m)) return {-1, m}; if(v->rx - v->lx == 1) return {v->lx, m}; } std::pair x{-1, monoid::template id()}; if(v->l) x = bisect_from_left(v->l, l, f, ok); if(x.first != -1) return x; if(v->r) x = bisect_from_left(v->r, l, f, ok); return x; } template std::pair bisect_from_right(node *v, const int r, const F &f, Val ok){ if(r < v->lx) return {-1, ok}; if(v->rx <= r + 1){ Val m = monoid::template merge(v->sum, ok); if(!f(m)) return {-1, m}; if(v->rx - v->lx == 1) return {v->lx, m}; } std::pair x{-1, monoid::template id()}; if(v->r) x = bisect_from_right(v->r, r, f, ok); if(x.first != -1) return x; if(v->l) x = bisect_from_right(v->l, r, f, ok); return x; } node *root; public: sparse_segment_tree(): root(nullptr){} sparse_segment_tree(int min_x, int max_x){ root = make_node(min_x, max_x); } void set(int k, Val x){ assert(root); set(root, k, x); } Val get(int k){ assert(root); return get(root, k); } void update(int k, Val x){ assert(root); update(root, k, x); } Val query(int l, int r){ assert(root); return query(root, l, r); } // f(sum[l, r])がtrueになる最左のr. ない場合は-1 template int bisect_from_left(int l, const F &f){ assert(root && root->lx <= l && l < root->rx); assert(!f(monoid::template id())); return bisect_from_left(root, l, f, monoid::template id()).first; } // f(sum[l, r])がtrueになる最右のl. ない場合は-1 template int bisect_from_right(int r, const F &f){ assert(root && root->lx <= r && r < root->rx); assert(!f(monoid::template id())); return bisect_from_right(root, r, f, monoid::template id()).first; } }; struct point_add_range_sum{ template static T id(){ return 0; } template static T update(T a, T b){ return a + b; } template static T merge(T a, T b){ return a + b; } }; #include int main(){ std::cin.tie(nullptr); std::ios::sync_with_stdio(false); int n; std::cin >> n; sparse_segment_tree seg(0, 1000000001); long long ans = 0; for(int i = 0; i < n; i++){ int a, b, c; std::cin >> a >> b >> c; if(!a){ seg.update(b, c); }else{ ans += seg.query(b, c + 1); } } std::cout << ans << '\n'; }