#include #include #include template struct sparse_segment_tree{ private: struct node{ int idx; node *l, *r; Val val, sum; node(int idx, Val val): idx(idx), l(nullptr), r(nullptr), val(val), sum(val){} }; node *make_node(int idx, Val val = monoid::template id()){ return new node(idx, val); } void eval(node *v){ v->sum = v->val; if(v->l) v->sum = monoid::template merge(v->l->sum, v->sum); if(v->r) v->sum = monoid::template merge(v->sum, v->r->sum); } void set(node* &v, int k, Val x, int l, int r){ if(!v){ v = make_node(k, x); return; } if(v->idx == k){ v->val = x; eval(v); return; } int mid = ((long long)l + r) >> 1; if(k < mid){ if(v->idx < k) std::swap(v->idx, k), std::swap(v->val, x); set(v->l, k, x, l, mid); }else{ if(v->idx > k) std::swap(v->idx, k), std::swap(v->val, x); set(v->r, k, x, mid, r); } eval(v); } Val get(node *v, int k, int l, int r){ if(!v) return monoid::template id(); if(v->idx == k) return v->val; int mid = ((long long)l + r) >> 1; if(k < mid) return get(v->l, k, l, mid); else return get(v->r, k, mid, r); } void update(node* &v, int k, Val x, int l, int r){ if(!v){ v = make_node(k, x); return; } if(v->idx == k){ v->val = monoid::template merge(v->val, x); eval(v); return; } int mid = ((long long)l + r) >> 1; if(k < mid){ if(v->idx < k) std::swap(v->idx, k), std::swap(v->val, x); update(v->l, k, x, l, mid); }else{ if(v->idx > k) std::swap(v->idx, k), std::swap(v->val, x); update(v->r, k, x, mid, r); } eval(v); } Val query(node *v, int a, int b, int l, int r){ if(!v || b <= l || r <= a) return monoid::template id(); if(a <= l && r <= b) return v->sum; int mid = ((long long)l + r) >> 1; Val ret = query(v->l, a, b, l, mid); if(a <= v->idx && v->idx < b) ret = monoid::template merge(ret, v->val); return monoid::template merge(ret, query(v->r, a, b, mid, 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; int minx, maxx; public: sparse_segment_tree(): root(nullptr), minx(0), maxx(0){} sparse_segment_tree(int minx, int maxx): root(nullptr), minx(minx), maxx(maxx){} void set(int k, Val x){ set(root, k, x, minx, maxx); } Val get(int k){ return get(root, k, minx, maxx); } void update(int k, Val x){ update(root, k, x, minx, maxx); } Val query(int l, int r){ return query(root, l, r, minx, maxx); } // f(sum[l, r])がtrueになる最左のr. ない場合は-1 template int bisect_from_left(int l, const F &f){ 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(!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'; }