#include #include #include #include #include #include #include using namespace std; typedef long long ll; const ll INF = 1e7; template class SegmentTreeBeats{ int n,hi; static const T idm=numeric_limits::min(); static const T idM=numeric_limits::max(),idl=idM; struct Node{ T Max,Max_second,Min,Min_second,sum,laz_val,laz_add; int Max_count,Min_count,len; Node():Max(idm),Max_second(idm),Min(idM),Min_second(idM) ,laz_val(idl),laz_add(0),len(1){} }; vector Nodes; inline void calc(int k){ Node &p=Nodes[k]; Node l=Nodes[k<<1|0]; Node r=Nodes[k<<1|1]; p.sum=l.sum+r.sum; if (l.Max=n) return; Node &p=Nodes[k]; if (p.laz_val!=idl){ update_node_val(k<<1|0,p.laz_val); update_node_val(k<<1|1,p.laz_val); p.laz_val=idl; return; } if (p.laz_add!=0){ update_node_add(k<<1|0,p.laz_add); update_node_add(k<<1|1,p.laz_add); p.laz_add=0; } if (p.Maxkc;) propagate(k>>i); } inline void thrust(int l,int r){ if (r==n<<1){thrust(l); return;} int h=hi,x=l^r; for (;!(x>>--h)&&h;) propagate(l>>h); int lc=__builtin_ctz(l),rc=__builtin_ctz(r); for (int i=h+1;i-->lc;) propagate(l>>i); for (int i=h+1;i-->rc;) propagate(r>>i); } inline void recalc(int k){ k>>=__builtin_ctz(k); while(k>>=1) calc(k); } public: SegmentTreeBeats(int n_){init(n_);} void init(int n_){ n=hi=1; while(n &v){ for (int i=0;i=b) return; thrust(a+=n),thrust(b+=n); for (int l=a,r=b;l>=1,r>>=1){ if (l&1) update_sub_min(l++,x); if (r&1) update_sub_min(--r,x); } recalc(a),recalc(b); } void update_max(int a,int b,T x){ if (a>=b) return; thrust(a+=n),thrust(b+=n); for (int l=a,r=b;l>=1,r>>=1){ if (l&1) update_sub_max(l++,x); if (r&1) update_sub_max(--r,x); } recalc(a),recalc(b); } void update_add(int a,int b,T x){ if (a>=b) return; thrust(a+=n),thrust(b+=n); for (int l=a,r=b;l>=1,r>>=1){ if (l&1) update_node_add(l++,x); if (r&1) update_node_add(--r,x); } recalc(a),recalc(b); } void update_val(int a,int b,T x){ if (a>=b) return; thrust(a+=n),thrust(b+=n); for (int l=a,r=b;l>=1,r>>=1){ if (l&1) update_node_val(l++,x); if (r&1) update_node_val(--r,x); } recalc(a),recalc(b); } T query_min(int a,int b){ if (a>=b) return idM; thrust(a+=n),thrust(b+=n); T vl=idM,vr=idM; for (int l=a,r=b;l>=1,r>>=1){ if (l&1) vl=min(vl,Nodes[l++].Min); if (r&1) vr=min(vr,Nodes[--r].Min); } return min(vl,vr); } T query_max(int a,int b){ if (a>=b) return idm; thrust(a+=n),thrust(b+=n); T vl=idm,vr=idm; for (int l=a,r=b;l>=1,r>>=1){ if (l&1) vl=max(vl,Nodes[l++].Max); if (r&1) vr=max(vr,Nodes[--r].Max); } return max(vl,vr); } T query_sum(int a,int b){ if (a>=b) return 0; thrust(a+=n),thrust(b+=n); T vl=0,vr=0; for (int l=a,r=b;l>=1,r>>=1){ if (l&1) vl+=Nodes[l++].sum; if (r&1) vr+=Nodes[--r].sum; } return vl+vr; } T operator[](int i){return Nodes[i+n].sum;} }; int N; int main(){ ios::sync_with_stdio(false); cin.tie(0); cout << setprecision(10) << fixed; cin >> N; int M = 40005; int K = 20000; vector a(M); SegmentTreeBeats sgt_max(M); SegmentTreeBeats sgt_min(M); sgt_max.build(a); sgt_min.build(a); for(int i = 0; i < N; i++){ ll x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; x1 += K; x2 += K; ll prev = sgt_max.query_sum(x1, x2+1)-sgt_min.query_sum(x1, x2+1); sgt_max.update_max(x1, x2, y2); sgt_min.update_min(x1, x2, y1); ll cur = sgt_max.query_sum(x1, x2+1)-sgt_min.query_sum(x1, x2+1); cout << cur-prev << endl; } }