#pragma GCC optimize("Ofast") #include #include #include using namespace std; using namespace __gnu_pbds; using ll = long long; using u64 = uint_fast64_t; using pii = pair; using pll = pair; #define rep(i, n) for(int i = 0; i < (n); ++i) #define all(x) (x).begin(),(x).end() constexpr char ln = '\n'; constexpr long long MOD = 1000000007; //constexpr long long MOD = 998244353; template inline bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return true;} return false; } template inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return true;} return false; } inline int popcount(int x) {return __builtin_popcount(x);} inline int popcount(long long x) {return __builtin_popcountll(x);} void print() { cout << "\n"; } template void print(const T &x, const Args &... args) { cout << x << " "; print(args...); } /////////////////////////////////////////////////////////////////////////////////////////////////////////////// constexpr int inf = 2e9; struct SegtreeBeats{ vectormx,smx,mxc; vectormn,smn,mnc; vectorsum,lazy; int size=1; void update_node_max(int k,int x){ sum[k]+=(x-mx[k])*mxc[k]; if(mx[k]==mn[k]){ mx[k]=mn[k]=x; }else if(mx[k]==smn[k]){ mx[k]=smn[k]=x; }else { mx[k]=x; } } void update_node_min(int k,int x){ sum[k]+=(x-mn[k])*mnc[k]; if(mx[k]==mn[k]){ mx[k]=mn[k]=x; }else if(smx[k]==mn[k]){ smx[k]=mn[k]=x; }else { mn[k]=x; } } void update_node_add(int k,int len,int x){ mx[k]+=x; if(smx[k]!=-inf)smx[k]+=x; mn[k]+=x; if(smn[k]!=inf)smn[k]+=x; sum[k]+=x*len; lazy[k]+=x; } void push(int k,int len){ if(k>=size-1)return; if(lazy[k]!=0){ update_node_add(k*2+1,len/2,lazy[k]); update_node_add(k*2+2,len/2,lazy[k]); lazy[k]=0; } if(mx[k*2+1]>mx[k])update_node_max(k*2+1,mx[k]); if(mx[k*2+2]>mx[k])update_node_max(k*2+2,mx[k]); if(mn[k*2+1]mx[2*k+2]){ mx[k]=mx[2*k+1]; mxc[k]=mxc[2*k+1]; smx[k]=max(smx[2*k+1],mx[2*k+2]); }else { mx[k]=mx[2*k+1]; mxc[k]=mxc[2*k+1]+mxc[2*k+2]; smx[k]=max(smx[2*k+1],smx[2*k+2]); } if(mn[2*k+1]mn[2*k+2]){ mn[k]=mn[2*k+2]; mnc[k]=mnc[2*k+2]; smn[k]=min(mn[2*k+1],smn[2*k+2]); }else { mn[k]=mn[2*k+1]; mnc[k]=mnc[2*k+1]+mnc[2*k+2]; smn[k]=min(smn[2*k+1],smn[2*k+2]); } } void update_min(int a,int b,int x,int k=0,int l=0,int r=-1){ if(r==-1)r=size; if(r<=a||b<=l||mx[k]<=x)return; if(a<=l&&r<=b&&smx[k]=x)return; if(a<=l&&r<=b&&smn[k]>x){ update_node_min(k,x); return; } push(k,r-l); update_max(a,b,x,k*2+1,l,(l+r)/2); update_max(a,b,x,k*2+2,(l+r)/2,r); update(k); } void update_add(int a,int b,int x,int k=0,int l=0,int r=-1){ if(r==-1)r=size; if(r<=a||b<=l)return; if(a<=l&&r<=b){ update_node_add(k,r-l,x); return; } push(k,r-l); update_add(a,b,x,k*2+1,l,(l+r)/2); update_add(a,b,x,k*2+2,(l+r)/2,r); update(k); } void set(int k,int x){ k+=size-1; mx[k]=x;mn[k]=x;sum[k]=x; } void init(){ for(int i=size-2;i>=0;i--)update(i); } int query_sum(int a,int b,int k=0,int l=0,int r=-1){ if(r==-1)r=size; if(r<=a||b<=l)return 0; if(a<=l&&r<=b)return sum[k]; push(k,r-l); int lv=query_sum(a,b,k*2+1,l,(l+r)/2); int rv=query_sum(a,b,k*2+2,(l+r)/2,r); return lv+rv; } SegtreeBeats(int x){ while(size> N; SegtreeBeats seg1(MAX),seg2(MAX); //cout << "!!!" << endl; rep(i,MAX) { seg1.set(i,0); seg2.set(i,0); } seg1.init(); seg2.init(); ll val = 0; rep(_,N) { int x1,y1,x2,y2; cin >> x1 >> y1 >> x2 >> y2; x1 += 20000; x2 += 20000; seg1.update_max(x1,x2,-y1); seg2.update_max(x1,x2,y2); ll cur = seg1.query_sum(0,40000) + seg2.query_sum(0,40000); cout << cur - val << ln; val = cur; } }