#include using namespace std; #define REP(i,a,n) for(int i=(a); i<(int)(n); i++) #define rep(i,n) REP(i,0,n) #define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it) #define ALLOF(c) (c).begin(), (c).end() typedef long long ll; typedef unsigned long long ull; template class LazySegmentTree { using FuncMM = std::function; using FuncMO = std::function; using FuncOO = std::function; const FuncMM funcMM; const FuncMO funcMO; const FuncOO funcOO; const Monoid monoidIdentity; const OpMonoid opMonoidIdentity; int N; std::vector dat; std::vector lazy; void setLazy(int k, const OpMonoid& om) { lazy[k] = funcOO(lazy[k], om); } void push(int k, int len) { if (lazy[k] == opMonoidIdentity) return; if (k < N) { setLazy(2 * k + 0, lazy[k]); setLazy(2 * k + 1, lazy[k]); } dat[k] = funcMO(dat[k], lazy[k], len); lazy[k] = opMonoidIdentity; } public: LazySegmentTree(int n, const FuncMM funcMM, const FuncMO funcMO, const FuncOO funcOO, const Monoid monoidIdentity, const OpMonoid opMonoidIdentity) : funcMM(funcMM), funcMO(funcMO), funcOO(funcOO), monoidIdentity(monoidIdentity), opMonoidIdentity(opMonoidIdentity) { N = 1; while (N < n) N *= 2; dat.resize(2 * N, monoidIdentity); lazy.resize(2 * N, opMonoidIdentity); } void dump() { std::cout << "dat: "; for (int i = 1; i < dat.size(); i++) { if (i == N) std::cout << "| "; std::cout << dat[i].ai << "(" << lazy[i].p << "," << lazy[i].q << "," << lazy[i].r << ") "; } std::cout << std::endl; } void set(int i, const Monoid& v) { dat[N + i] = v; } void init() { for (int i = N - 1; i > 0; i--) { dat[i] = funcMM(dat[2 * i + 0], dat[2 * i + 1]); } } void update(int s, int t, const OpMonoid& om) { update(s, t, om, 1, 0, N); } void update(int s, int t, const OpMonoid& om, int k, int l, int r) { push(k, r - l); if (r <= s || t <= l) return; if (s <= l && r <= t) { setLazy(k, om); push(k, r - l); return; } update(s, t, om, 2 * k + 0, l, (l + r) / 2); update(s, t, om, 2 * k + 1, (l + r) / 2, r); dat[k] = funcMM(dat[2 * k + 0], dat[2 * k + 1]); } Monoid query(int s, int t) { return query(s, t, 1, 0, N); } Monoid query(int s, int t, int k, int l, int r) { push(k, r - l); if (r <= s || t <= l) return monoidIdentity; if (s <= l && r <= t) return dat[k]; Monoid vl = query(s, t, 2 * k + 0, l, (l + r) / 2); Monoid vr = query(s, t, 2 * k + 1, (l + r) / 2, r); return funcMM(vl, vr); } }; struct VAL { ll ai; }; struct OP { ll p; }; bool operator==(const OP& a, const OP& b) { return a.p == b.p; } int find_i(LazySegmentTree& lst, ll h){ int lb = -1, ub = 20003; while(ub-lb>1){ int mid = (lb+ub)/2; if(lst.query(mid,mid+1).ai >= h) lb = mid; else ub = mid; } return ub; } ll solve(LazySegmentTree& lst, int x, int y){ x--; int xx = find_i(lst, y); if(x < xx) return 0; ll w = x+1-xx; ll sum = lst.query(xx,x+1).ai; ll ret = w * y - sum; OP op; op.p = y; lst.update(xx,x+1,op); return ret; } int main(){ auto funcMM = [](const VAL& a, const VAL& b) { VAL ret; ret.ai = a.ai + b.ai; return ret; }; auto funcMO = [](const VAL& a, const OP& b, int k) { VAL ret; ret.ai = b.p * k; return ret; }; auto funcOO = [](const OP& a, const OP& b) { OP ret; ret.p = b.p; return ret; }; LazySegmentTree lst1(20005, funcMM, funcMO, funcOO, (VAL){0}, (OP){0}); LazySegmentTree lst2(20005, funcMM, funcMO, funcOO, (VAL){0}, (OP){0}); LazySegmentTree lst3(20005, funcMM, funcMO, funcOO, (VAL){0}, (OP){0}); LazySegmentTree lst4(20005, funcMM, funcMO, funcOO, (VAL){0}, (OP){0}); int N; cin >> N; rep(i,N){ int Xa, Ya, Xb, Yb; cin >> Xa >> Ya >> Xb >> Yb; ll a = solve(lst1, Xb, Yb); ll b = solve(lst2, Xb, -Ya); ll c = solve(lst3, -Xa, -Ya); ll d = solve(lst4, -Xa, Yb); ll sum = a+b+c+d; //cout << a << " " << b << " " << c << " " << d << endl; cout << sum << endl; } return 0; }