// 解説見て解いた /** * @FileName a.cpp * @Author kanpurin * @Created 2020.06.06 00:06:19 **/ #include "bits/stdc++.h" using namespace std; typedef long long ll; template < typename Monoid > struct LazySegmentTree { private: using Func = std::function< Monoid(Monoid, Monoid) >; Func F = [](Monoid a, Monoid b) { return a + b; }; Monoid UNITY = 0; int n; std::vector< Monoid > node, lazy; std::vector< int > prop; void eval(int k, int l, int r) { if (prop[k] != 0) { node[k] = lazy[k] + (prop[k] == 1 ? node[k] : 0); if (r - l > 1) { lazy[2 * k + 1] = lazy[k] / 2 + (prop[k] == 1 ? lazy[2 * k + 1] : 0); lazy[2 * k + 2] = lazy[k] / 2 + (prop[k] == 1 ? lazy[2 * k + 2] : 0); prop[2 * k + 1] = prop[2 * k + 2] = prop[k]; } lazy[k] = 0; prop[k] = 0; } } public: LazySegmentTree(int m, Monoid val) { n = 1; while (n < m) n <<= 1; node.resize(n * 2 - 1, UNITY); lazy.resize(n * 2 - 1, 0); prop.resize(n * 2 - 1, 0); if (val != LazySegmentTree::UNITY) { for (int i = 0; i < m; i++) node[n + i - 1] = val; build(); } } LazySegmentTree(const std::vector< Monoid > &v) { int sz = v.size(); n = 1; while (n < sz) n <<= 1; node.resize(n * 2 - 1, UNITY); lazy.resize(n * 2 - 1, 0); prop.resize(n * 2 - 1, 0); for (int i = 0; i < sz; i++) node[i + n - 1] = v[i]; build(); } void set(int k, const Monoid &x) { node[n + k - 1] = x; } void build() { for (int i = n - 2; i >= 0; i--) node[i] = F(node[2 * i + 1], node[2 * i + 2]); } void add_query(int a, int b, Monoid x, int k = 0, int l = 0, int r = -1) { if (r < 0) r = n; eval(k, l, r); if (b <= l || r <= a) return; if (a <= l && r <= b) { prop[k] = 1; lazy[k] += (r - l) * x; eval(k, l, r); } else { add_query(a, b, x, 2 * k + 1, l, (r - l) / 2 + l); add_query(a, b, x, 2 * k + 2, (r - l) / 2 + l, r); node[k] = F(node[2 * k + 1], node[2 * k + 2]); } } void update_query(int a, int b, Monoid x, int k = 0, int l = 0, int r = -1) { if (r < 0) r = n; eval(k, l, r); if (b <= l || r <= a) return; if (a <= l && r <= b) { prop[k] = 2; lazy[k] = (r - l) * x; eval(k, l, r); } else { update_query(a, b, x, 2 * k + 1, l, (r - l) / 2 + l); update_query(a, b, x, 2 * k + 2, (r - l) / 2 + l, r); node[k] = F(node[2 * k + 1], node[2 * k + 2]); } } Monoid get_query(int a, int b, int k = 0, int l = 0, int r = -1) { if (r < 0) r = n; if (r <= a || b <= l) return UNITY; eval(k, l, r); if (a <= l && r <= b) return node[k]; Monoid vl = get_query(a, b, 2 * k + 1, l, (r - l) / 2 + l); Monoid vr = get_query(a, b, 2 * k + 2, (r - l) / 2 + l, r); return F(vl, vr); } Monoid operator[](int x) { return get_query(x, x + 1); } void print() { for (int i = 0; i < n; i++) { std::cout << i << "\t: " << get_query(i, i + 1) << std::endl; } } }; int main() { constexpr long long LLINF = 1e18 + 1; int n; cin >> n; const int limit = 20000; vector< LazySegmentTree< ll > > seg(4, LazySegmentTree< ll >(limit + 1, 0)); for (int i = 0; i < 4; i++) { seg[i].update_query(0, 1, LLINF); } for (int i = 0; i < n; i++) { ll ans = 0; int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; pair< int, int > v[] = {{x2, y2}, {-x1, y2}, {-x1, -y1}, {x2, -y1}}; for (int k = 0; k < 4; k++) { int x = v[k].first; int y = v[k].second; int l = 0, r = limit + 1; while (r - l > 1) { int mid = l + (r - l) / 2; if (seg[k][mid] < y) { r = mid; } else { l = mid; } } if (r > x) continue; ans -= seg[k].get_query(r, x + 1); seg[k].update_query(r, x + 1, y); ans += seg[k].get_query(r, x + 1); } cout << ans << endl; } return 0; }