#define PROBLEM "https://yukicoder.me/problems/no/789" #pragma region kyopro_template #define Nyaan_template #include #include #define pb push_back #define eb emplace_back #define fi first #define se second #define each(x, v) for (auto &x : v) #define all(v) (v).begin(), (v).end() #define sz(v) ((int)(v).size()) #define mem(a, val) memset(a, val, sizeof(a)) #define ini(...) \ int __VA_ARGS__; \ in(__VA_ARGS__) #define inl(...) \ long long __VA_ARGS__; \ in(__VA_ARGS__) #define ins(...) \ string __VA_ARGS__; \ in(__VA_ARGS__) #define inc(...) \ char __VA_ARGS__; \ in(__VA_ARGS__) #define in2(s, t) \ for (int i = 0; i < (int)s.size(); i++) { \ in(s[i], t[i]); \ } #define in3(s, t, u) \ for (int i = 0; i < (int)s.size(); i++) { \ in(s[i], t[i], u[i]); \ } #define in4(s, t, u, v) \ for (int i = 0; i < (int)s.size(); i++) { \ in(s[i], t[i], u[i], v[i]); \ } #define rep(i, N) for (long long i = 0; i < (long long)(N); i++) #define repr(i, N) for (long long i = (long long)(N)-1; i >= 0; i--) #define rep1(i, N) for (long long i = 1; i <= (long long)(N); i++) #define repr1(i, N) for (long long i = (N); (long long)(i) > 0; i--) #define reg(i, a, b) for (long long i = (a); i < (b); i++) #define die(...) \ do { \ out(__VA_ARGS__); \ return; \ } while (0) using namespace std; using ll = long long; template using V = vector; using vi = vector; using vl = vector; using vvi = vector>; using vd = V; using vs = V; using vvl = vector>; using P = pair; using vp = vector

; using pii = pair; using vpi = vector>; constexpr int inf = 1001001001; constexpr long long infLL = (1LL << 61) - 1; template inline bool amin(T &x, U y) { return (y < x) ? (x = y, true) : false; } template inline bool amax(T &x, U y) { return (x < y) ? (x = y, true) : false; } template ostream &operator<<(ostream &os, const pair &p) { os << p.first << " " << p.second; return os; } template istream &operator>>(istream &is, pair &p) { is >> p.first >> p.second; return is; } template ostream &operator<<(ostream &os, const vector &v) { int s = (int)v.size(); for (int i = 0; i < s; i++) os << (i ? " " : "") << v[i]; return os; } template istream &operator>>(istream &is, vector &v) { for (auto &x : v) is >> x; return is; } void in() {} template void in(T &t, U &... u) { cin >> t; in(u...); } void out() { cout << "\n"; } template void out(const T &t, const U &... u) { cout << t; if (sizeof...(u)) cout << " "; out(u...); } #ifdef NyaanDebug #define trc(...) \ do { \ cerr << #__VA_ARGS__ << " = "; \ dbg_out(__VA_ARGS__); \ } while (0) #define trca(v, N) \ do { \ cerr << #v << " = "; \ array_out(v, N); \ } while (0) #define trcc(v) \ do { \ cerr << #v << " = {"; \ each(x, v) { cerr << " " << x << ","; } \ cerr << "}" << endl; \ } while (0) template void _cout(const T &c) { cerr << c; } void _cout(const int &c) { if (c == 1001001001) cerr << "inf"; else if (c == -1001001001) cerr << "-inf"; else cerr << c; } void _cout(const unsigned int &c) { if (c == 1001001001) cerr << "inf"; else cerr << c; } void _cout(const long long &c) { if (c == 1001001001 || c == (1LL << 61) - 1) cerr << "inf"; else if (c == -1001001001 || c == -((1LL << 61) - 1)) cerr << "-inf"; else cerr << c; } void _cout(const unsigned long long &c) { if (c == 1001001001 || c == (1LL << 61) - 1) cerr << "inf"; else cerr << c; } template void _cout(const pair &p) { cerr << "{ "; _cout(p.fi); cerr << ", "; _cout(p.se); cerr << " } "; } template void _cout(const vector &v) { int s = v.size(); cerr << "{ "; for (int i = 0; i < s; i++) { cerr << (i ? ", " : ""); _cout(v[i]); } cerr << " } "; } template void _cout(const vector> &v) { cerr << "[ "; for (const auto &x : v) { cerr << endl; _cout(x); cerr << ", "; } cerr << endl << " ] "; } void dbg_out() { cerr << endl; } template void dbg_out(const T &t, const U &... u) { _cout(t); if (sizeof...(u)) cerr << ", "; dbg_out(u...); } template void array_out(const T &v, int s) { cerr << "{ "; for (int i = 0; i < s; i++) { cerr << (i ? ", " : ""); _cout(v[i]); } cerr << " } " << endl; } template void array_out(const T &v, int H, int W) { cerr << "[ "; for (int i = 0; i < H; i++) { cerr << (i ? ", " : ""); array_out(v[i], W); } cerr << " ] " << endl; } #else #define trc(...) #define trca(...) #define trcc(...) #endif inline int popcnt(unsigned long long a) { return __builtin_popcountll(a); } inline int lsb(unsigned long long a) { return __builtin_ctzll(a); } inline int msb(unsigned long long a) { return 63 - __builtin_clzll(a); } template inline int getbit(T a, int i) { return (a >> i) & 1; } template inline void setbit(T &a, int i) { a |= (1LL << i); } template inline void delbit(T &a, int i) { a &= ~(1LL << i); } template int lb(const vector &v, const T &a) { return lower_bound(begin(v), end(v), a) - begin(v); } template int ub(const vector &v, const T &a) { return upper_bound(begin(v), end(v), a) - begin(v); } template int btw(T a, T x, T b) { return a <= x && x < b; } template T ceil(T a, U b) { return (a + b - 1) / b; } constexpr long long TEN(int n) { long long ret = 1, x = 10; while (n) { if (n & 1) ret *= x; x *= x; n >>= 1; } return ret; } template vector mkrui(const vector &v) { vector ret(v.size() + 1); for (int i = 0; i < int(v.size()); i++) ret[i + 1] = ret[i] + v[i]; return ret; }; template vector mkuni(const vector &v) { vector ret(v); sort(ret.begin(), ret.end()); ret.erase(unique(ret.begin(), ret.end()), ret.end()); return ret; } template vector mkord(int N, F f) { vector ord(N); iota(begin(ord), end(ord), 0); sort(begin(ord), end(ord), f); return ord; } template vector mkiota(int N) { vector ret(N); iota(begin(ret), end(ret), 0); return ret; } template vector mkinv(vector &v) { vector inv(v.size()); for (int i = 0; i < (int)v.size(); i++) inv[v[i]] = i; return inv; } struct IoSetupNya { IoSetupNya() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); cerr << fixed << setprecision(7); } } iosetupnya; void solve(); int main() { solve(); } #pragma endregion using namespace std; template struct DynamicSegmentTree { using ll = long long; struct Node { T data; Node *l, *r; Node() {} Node(const T &_data) : data(_data), l(nullptr), r(nullptr) {} }; Node *pool; int pid; ll L, R; const F &f; const T ID; Node *root; DynamicSegmentTree(const vector &v, const F &_f, const T &_ID) : pid(0), L(0), R((ll)v.size()), f(_f), ID(_ID) { pool = new Node[NODES]; root = build(v); } DynamicSegmentTree(const ll &_L, const ll &_R, const F &_f, const T &_ID) : pid(0), L(_L), R(_R), f(_f), ID(_ID) { pool = new Node[NODES]; root = my_new(ID); } Node *my_new(const T &data) { pool[pid].data = data; pool[pid].l = pool[pid].r = nullptr; return &(pool[pid++]); } Node *my_new(Node *l, Node *r) { pool[pid].data = f(l->data, r->data); pool[pid].l = l; pool[pid].r = r; return &(pool[pid++]); } Node *build(const vector &v) { return build(L, R, v); } Node *build(ll l, ll r, const vector &v) { if (l + 1 == r) return my_new(v[l]); ll m = (l + r) >> 1; return my_new(build(l, m, v), build(m, r, v)); } void _update(ll a, const T &x, Node *n, ll l, ll r) { if (l + 1 == r) { n->data = x; return; } ll m = (l + r) >> 1; if (a < m) { if (!n->l) n->l = my_new(ID); _update(a, x, n->l, l, m); } else { if (!n->r) n->r = my_new(ID); _update(a, x, n->r, m, r); } n->data = f(n->l ? (n->l)->data : ID, n->r ? (n->r)->data : ID); } void update(ll k, const T &x) { _update(k, x, root, L, R); } void add(ll k, const T &x) { Node *n = root; ll l = L, r = R; n->data = f(n->data, x); while (r - l > 1) { ll m = (l + r) >> 1; if (k < m) { if (!n->l) n->l = my_new(ID); n = n->l; r = m; } else { if (!n->r) n->r = my_new(ID); n = n->r; l = m; } n->data = f(n->data, x); } } T _query(ll a, ll b, Node *n, ll l, ll r) { if (r <= a or b <= l) return ID; if (a <= l and r <= b) return n->data; ll m = (l + r) >> 1; return f(n->l ? _query(a, b, n->l, l, m) : ID, n->r ? _query(a, b, n->r, m, r) : ID); } T query(ll a, ll b) { return _query(a, b, root, L, R); } }; void solve() { ini(N); auto f = [](ll a, ll b) { return a + b; }; DynamicSegmentTree seg(-100, inf, f, 0); ll ans = 0; rep(_, N) { inl(c, x, y); if (c == 0) { seg.add(x, y); } else { ans += seg.query(x, y + 1); } } out(ans); }