#include using namespace std; /* #include using namespace boost::multiprecision; using cint = cpp_int; */ // Define using ll = long long; using ull = unsigned long long; using ld = long double; const ll dx[4] = {1, 0, -1, 0}; const ll dy[4] = {0, 1, 0, -1}; const ll MOD = 1e9 + 7; const ll inf = 1 << 30; // const ll INF = LONG_MAX; const ll INF = 1LL << 60; const ull MAX = ULONG_MAX; #define mp make_pair #define pb push_back #define eb emplace_back #define endl '\n' #define space ' ' #define def inline auto #define func inline constexpr ll #define run(a) __attribute__((constructor)) def _##a() #define all(v) begin(v), end(v) #define input(a) scanf("%lld", &(a)) #define print(a) printf("%lld\n", (a)) #define fi first #define se second #define ok(a, b) (0 <= (a) && (a) < (b)) template using vvector = vector>; template using rpriority_queue = priority_queue, greater>; // Debug #define debug(...) \ { \ cerr << __LINE__ << ": " << #__VA_ARGS__ << " = "; \ for (auto &&X : {__VA_ARGS__}) cerr << "[" << X << "] "; \ cerr << endl; \ } #define dump(a, h, w) \ { \ cerr << __LINE__ << ": " << #a << " = [" << endl; \ rep(__i, h) { \ rep(__j, w) cerr << a[__i][__j] << space; \ cerr << endl; \ } \ cerr << "]" << endl; \ } #define vdump(a, n) \ { \ cerr << __LINE__ << ": " << #a << " = ["; \ rep(__i, n) if (__i) cerr << space << a[__i]; \ else cerr << a[__i]; \ cerr << "]" << endl; \ } struct edge { ll to, cost; edge(ll a, ll b) : to(a), cost(b) {} }; struct position { ll x, y; position() {} position(ll a, ll b) : x(a), y(b) {} position next(ll i) { return {x + dx[i], y + dy[i]}; } ll mdist() { return abs(x) + abs(y); } double dist() { return sqrt(x * x + y * y); } double norm(ll d) { if (d == inf) return max(x, y); if (d == 1) return mdist(); if (d == 2) return dist(); return 0; } ll num(ll width) { return abs(x) * width + abs(y); } bool operator==(position a) { return x == a.x && y == a.y; } bool operator!=(position a) { return x != a.x || y != a.y; } bool operator<(position a) { return x < a.x && y < a.y; } bool operator>(position a) { return x > a.x && y > a.y; } bool operator<=(position a) { return x <= a.x && y <= a.y; } bool operator>=(position a) { return x >= a.x && y >= a.y; } position operator+(position a) { return position(x + a.x, y + a.y); } position operator-(position a) { return position(x - a.x, y - a.y); } position operator*(position a) { return position(x * a.x, y * a.y); } position operator/(position a) { return position(x / a.x, y / a.y); } position operator%(position a) { return position(x % a.x, y % a.y); } position complex(position a) { return position(x * a.x - y * a.y, x * a.y + y * a.x); } /* // for sort: bool operator<(position a) { return x ^ a.x ? x < a.x : y < a.y; } bool operator>(position a) { return x ^ a.x ? x > a.x : y > a.y; } bool operator<=(position a) { return x ^ a.x ? x < a.x : y <= a.y; } bool operator>=(position a) { return x ^ a.x ? x > a.x : y >= a.y; } */ }; position Origin = position(0, 0); using pos = position; using vec = position; struct Range { ll left, right; Range() {} Range(ll l, ll r) : left(l), right(r) {} ll length() { return right - left; } bool operator==(Range A) { return left == A.left && right == A.right; } bool operator!=(Range A) { return !(Range(left, right) == A); } bool operator>(Range A) { return left < A.left && right > A.right; } bool operator<(Range A) { return left > A.left && right < A.right; } bool operator>=(Range A) { return left <= A.left && right >= A.right; } bool operator<=(Range A) { return left >= A.left && right <= A.right; } }; // Loop #define inc(i, a, n) for (ll i = (a), _##i = (n); i <= _##i; ++i) #define dec(i, a, n) for (ll i = (a), _##i = (n); i >= _##i; --i) #define rep(i, n) for (ll i = 0, _##i = (n); i < _##i; ++i) #define each(i, a) for (auto &&i : a) #define loop() for (;;) // Stream #define fout(n) cout << fixed << setprecision(n) #define fasten cin.tie(0), ios::sync_with_stdio(0) // Speed run(0) { fasten, fout(10); } #pragma GCC optimize("O3") #pragma GCC target("avx") // Math //#define gcd __gcd func gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; } func lcm(ll a, ll b) { return a * b / gcd(a, b); } func sign(ll a) { return a ? abs(a) / a : 0; } template def in() { T A; cin >> A; return A; } template def out(vector> A, ll H, ll W, char divc = space, char endc = endl) { rep(i, H) { rep(j, W) { if (j) cout << divc << A[i][j]; else cout << A[i][j]; } cout << endc; } } struct SegTree { vector data, delay; vector range; SegTree(ll size) : data(size), delay(size), range(size) { fill(all(data), 0); fill(all(delay), 0); fill(all(range), Range(0, 0)); data[0] = size; } ll parent(ll id) { return id >> 1; } ll childleft(ll id) { return id << 1; } ll childright(ll id) { return childleft(id) + 1; } Range itor(ll id) { if (id == 1) return Range(0, parent(data[0])); if (range[id].length()) return range[id]; Range ran = itor(parent(id)); if (id & 1) ran.left += ran.length() / 2; else ran.right -= ran.length() / 2; return range[id] = ran; } void delayed(ll id) { ll c1 = childleft(id), c2 = childright(id); if (ok(c1, data[0])) { data[c1] += delay[id] * itor(c1).length(); delay[c1] += delay[id]; } if (ok(c2, data[0])) { data[c2] += delay[id] * itor(c2).length(); delay[c2] += delay[id]; } delay[id] = 0; } void add(ll val, Range ran, ll id = 1) { delayed(id); Range idran = itor(id); if (ran == idran) { data[id] += val * ran.length(); delay[id] += val; } else { ll mid = (idran.left + idran.right) / 2; if (ran.right <= mid) { add(val, ran, childleft(id)); data[id] += val * ran.length(); } else if (ran.left >= mid) { add(val, ran, childright(id)); data[id] += val * ran.length(); } else { Range lran(ran.left, mid), rran(mid, ran.right); add(val, lran, childleft(id)); add(val, rran, childright(id)); data[id] += val * ran.length(); } } } ll sum(Range ran, ll id = 1) { ll res = 0; delayed(id); Range idran = itor(id); if (ran == idran) { res = data[id]; } else { ll mid = (idran.left + idran.right) / 2; if (ran.right <= mid) { res = sum(ran, childleft(id)); } else if (ran.left >= mid) { res = sum(ran, childright(id)); } else { Range lran(ran.left, mid), rran(mid, ran.right); res += sum(lran, childleft(id)); res += sum(rran, childright(id)); } } return res; } ll at(ll at) { return sum(Range(at, at + 1)); } }; ll segsize(ll N) { ll lg = ceil(log2(N)); return 1 << (lg + 1); } signed main() { ll N; cin >> N; ll res = 0, A[N], B[N], C[N]; vector at; rep(i, N) { cin >> A[i] >> B[i] >> C[i]; if (!A[i]) at.pb(B[i]); } sort(all(at)); ll S = at.size(); SegTree Seg(segsize(S + 1)); rep(i, N) { if (A[i]) { ll l = lower_bound(all(at), B[i]) - at.begin(); ll r = lower_bound(all(at), C[i] + 1) - at.begin(); res += Seg.sum(Range(l, r)); } else { ll l = lower_bound(all(at), B[i]) - at.begin(); Seg.add(C[i], Range(l, l + 1)); } debug(res); } cout << res << endl; } // for compilation: g++ -Ofast -march=native -o _ _.cpp -std=c++17