#include #include #include #include #include using namespace std; #define all(x) (x).begin(), (x).end() template< typename Monoid > struct SegmentTree { using F = function< Monoid(Monoid, Monoid) >; int sz; vector< Monoid > seg; const F f; const Monoid M1; SegmentTree(int n, const F f, const Monoid &M1) : f(f), M1(M1) { sz = 1; while(sz < n) sz <<= 1; seg.assign(2 * sz, M1); } void set(int k, const Monoid &x) { seg[k + sz] = x; } void build() { for(int k = sz - 1; k > 0; k--) { seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]); } } void update(int k, const Monoid &x) { k += sz; seg[k] = x; while(k >>= 1) { seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]); } } Monoid query(int a, int b) { Monoid L = M1, R = M1; for(a += sz, b += sz; a < b; a >>= 1, b >>= 1) { if(a & 1) L = f(L, seg[a++]); if(b & 1) R = f(seg[--b], R); } return f(L, R); } Monoid operator[](const int &k) const { return seg[k + sz]; } }; int main(){ int n; cin >> n; vector x; int queries[n][3]; for(int i = 0; i < n; i++){ for(int j = 0; j < 3; j++){ cin >> queries[i][j]; } if(!queries[i][0]){ x.push_back(queries[i][1]); } } sort(all(x)); x.erase(unique(all(x)), x.end()); int nums[x.size()]; for(int i = 0; i < x.size(); i++){ nums[i] = 0; } SegmentTree< int > seg(n, [](int a, int b){ return a + b; }, 0); for(int i = 0; i < n; i++){ seg.set(i, 0); } seg.build(); long ans = 0; for(int i = 0; i < n; i++){ if(!queries[i][0]){ int point = int(lower_bound(all(x), queries[i][1]) - x.begin()); nums[point] += queries[i][2]; seg.update(point, nums[point]); }else{ int left = int(lower_bound(all(x), queries[i][1]) - x.begin()); int right = int(upper_bound(all(x), queries[i][2]) - x.begin()); ans += seg.query(left, right); } } cout << ans << endl; }