#line 2 "sparse_bit.hpp" #include #include #include #include template struct sparse_binary_indexed_tree{ private: using I = int; static constexpr int bitlen = sizeof(I) * 8; // idxの2進数においてk-bitから下位bitに向けて1がいくつ続くか static int count_consecutive_one(I idx, int k){ static_assert(bitlen == 32 || bitlen == 64); if(bitlen == 32) return __builtin_clz(~((uint32_t)idx << (31 - k))); return __builtin_clzll(~((uint64_t)idx << (63 - k))); } static int count_trailing_one(I idx){ static_assert(bitlen == 32 || bitlen == 64); if(bitlen == 32) return __builtin_ctz(~(uint32_t)idx); return __builtin_ctzll(~(uint64_t)idx); } I maxn; int h; struct node{ I idx; std::vector ch; Val val, sum; node(I idx, Val val): idx(idx), val(val), sum(val){} }; node *root; void update(node* &v, I idx, Val x, int h_cur){ if(!v){ v = new node(idx, x); return; }else if(v->idx == idx){ v->val += x; v->sum += x; return; }else v->sum += x; if(h_cur == -1 || count_trailing_one(idx) == h_cur + 1) return; // 残りの下位bitが全て1なら終了 int k = count_consecutive_one(idx, h_cur); int t = count_consecutive_one(v->idx, h_cur); bool f = false; if(v->idx > idx){ if(k || t) f = true; }else if(!k && !t) f = true; if(f) std::swap(v->idx, idx), std::swap(v->val, x), std::swap(k, t); if(v->ch.size() <= k) v->ch.resize(k + 1, nullptr); update(v->ch[k], idx, x, h_cur - 1 - k); } Val query(node *v, I idx, int h_cur){ if(!v || h_cur == -1) return Val(0); Val res = v->idx < idx ? v->val : Val(0); int k = count_consecutive_one(idx, h_cur); int maxk = std::min(k, (int)v->ch.size()); for(int i = 0; i < maxk; i++) if(v->ch[i]) res += v->ch[i]->sum; if(v->ch.size() > k) res += query(v->ch[k], idx, h_cur - 1 - k); return res; } public: sparse_binary_indexed_tree(): root(nullptr){} // [0, n) sparse_binary_indexed_tree(I n): root(nullptr){ n = std::max(n + 1, 2); maxn = 1, h = 0; while(maxn < n) maxn <<= 1, h++; } void update(I idx, Val x){ assert(0 <= idx && idx < maxn); update(root, idx, x, h - 1); } Val query(I r){ assert(0 <= r && r <= maxn); return query(root, r, h - 1); } Val query(I l, I r){ assert(0 <= l && l <= r && r <= maxn); if(l == r) return Val(0); return query(root, r, h - 1) - query(root, l, h - 1); } }; #line 3 ".lib/template.hpp" #include #line 5 ".lib/template.hpp" #include #include #include #include #include #line 11 ".lib/template.hpp" #include #include #include #include #include #include #include #line 19 ".lib/template.hpp" #include #include #include #include #include #define allof(obj) (obj).begin(), (obj).end() #define range(i, l, r) for(int i=l;i>1)|y_bit)) #define bit_kth(i, k) ((i >> k)&1) #define bit_highest(i) (i?63-__builtin_clzll(i):-1) #define bit_lowest(i) (i?__builtin_ctzll(i):-1) using ll = long long; using ld = long double; using ul = uint64_t; using pi = std::pair; using pl = std::pair; template using vec = std::vector; using namespace std; template std::ostream &operator<<(std::ostream &dest, const std::pair &p){ dest << p.first << ' ' << p.second; return dest; } template std::ostream &operator<<(std::ostream &dest, const std::vector> &v){ int sz = v.size(); if(sz==0) return dest; for(int i=0;i std::ostream &operator<<(std::ostream &dest, const std::vector &v){ int sz = v.size(); if(sz==0) return dest; for(int i=0;i std::ostream &operator<<(std::ostream &dest, const std::array &v){ if(sz==0) return dest; for(int i=0;i std::ostream &operator<<(std::ostream &dest, const std::set &v){ for(auto itr=v.begin();itr!=v.end();){ dest << *itr; itr++; if(itr!=v.end()) dest << ' '; } return dest; } template std::ostream &operator<<(std::ostream &dest, const std::map &v){ for(auto itr=v.begin();itr!=v.end();){ dest << '(' << itr->first << ", " << itr->second << ')'; itr++; if(itr!=v.end()) dest << '\n'; } return dest; } template vector make_vec(size_t sz, T val){return std::vector(sz, val);} template auto make_vec(size_t sz, Tail ...tail){ return std::vector(tail...))>(sz, make_vec(tail...)); } template vector read_vec(size_t sz){ std::vector v(sz); for(int i=0;i> v[i]; return v; } template auto read_vec(size_t sz, Tail ...tail){ auto v = std::vector(tail...))>(sz); for(int i=0;i(tail...); return v; } void io_init(){ std::cin.tie(nullptr); std::ios::sync_with_stdio(false); } #line 3 "a.cpp" #line 5 "a.cpp" int main(){ std::cin.tie(nullptr); std::ios::sync_with_stdio(false); int n; std::cin >> n; sparse_binary_indexed_tree t(1000000001); long long ans = 0; for(int i = 0; i < n; i++){ int a, b, c; std::cin >> a >> b >> c; if(!a){ t.update(b, c); }else{ ans += t.query(b, c + 1); } } std::cout << ans << '\n'; }