#include using namespace std; typedef long long ll; #define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i) #define ALL(v) (v).begin(),(v).end() #define CLR(t,v) memset(t,(v),sizeof(t)) templateostream& operator<<(ostream& os,const pair&a){return os<<"("<void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<void chmin(T&a,const T&b){if(a>b)a=b;} templatevoid chmax(T&a,const T&b){if(a seg; vector lazy; const Val UNITY_LAZY = -1; void clear(int N) { for (n = 1; n < N; n <<= 1); seg.assign(n * 2, 0); lazy.assign(n * 2, UNITY_LAZY); seg[1] = 0; // 初期値 } void eval_lazy(int nl, int nr, int k) { if (lazy[k] != UNITY_LAZY) { seg[k] = (nr - nl) * lazy[k]; if (nr - nl >= 2) { lazy[2*k ] = lazy[k]; lazy[2*k+1] = lazy[k]; } lazy[k] = UNITY_LAZY; } } // [l, r) の和 Val getSum(int l, int r) { if (r - l <= 0) return 0; return getSum(0, n, 1, l, r); } Val getSum(int nl, int nr, int k, int l, int r) { eval_lazy(nl, nr, k); if (r <= nl || nr <= l) return 0; if (l <= nl && nr <= r) { return seg[k]; } Val x = getSum(nl, (nl+nr)/2, 2*k , l, r); Val y = getSum((nl+nr)/2, nr, 2*k+1, l, r); return x + y; } // [l, r) の全てを val で更新 void updateRange(int l, int r, Val val) { updateRange(0, n, 1, l, r, val); } void updateRange(int nl, int nr, int k, int l, int r, Val val) { eval_lazy(nl, nr, k); if (r <= nl || nr <= l) return; if (l <= nl && nr <= r) { lazy[k] = val; eval_lazy(nl, nr, k); return; } updateRange(nl, (nl+nr)/2, 2*k , l, r, val); updateRange((nl+nr)/2, nr, 2*k+1, l, r, val); seg[k] = seg[2*k] + seg[2*k+1]; } }; int main2() { RangeUpdateRangeSum segTree[4]; const int MAX_C = 41234; REP(i, 4) segTree[i].clear(MAX_C); int N = nextLong(); REP(i, N) { int Xa = nextLong(); int Ya = nextLong(); int Xb = nextLong(); int Yb = nextLong(); int Xs[4] = { Xb, abs(Xa), abs(Xa), Xb }; int Ys[4] = { Yb, Yb, abs(Ya), abs(Ya) }; ll ans = 0; REP(i, 4) { const int X = Xs[i]; const int Y = Ys[i]; ll x = segTree[i].getSum(0, X); ll hi = MAX_C; ll lo = -1; while (hi - lo > 1) { ll mi = (hi + lo) / 2; if (Y > segTree[i].getSum(mi, mi+1)) { hi = mi; } else { lo = mi; } } if (hi < X) { segTree[i].updateRange(hi, X, Y); } ll y = segTree[i].getSum(0, X); ans += y - x; // cout << "i=" << i << " +" << y-x << endl; } cout << ans << endl; } return 0; } int main() { #ifdef LOCAL for (;!cin.eof();cin>>ws) #endif main2(); return 0; }