C++ 解法, 执行用时: 6128ms, 内存消耗: 30252K, 提交时间: 2022-03-26 17:45:54

#include<bits/stdc++.h>
#define F(i,l,r) for(int i=l;i<r;++i)
#define Fe(i,l,r) for(int i=l;i<=r;++i)

using std::max;
int read(int L,int R){
	int x;
	assert(scanf("%d",&x)==1);
	return x;
}
constexpr int maxm=5e5,M=maxm+10,maxv=1e9;
typedef long long i64;

const int MEM=1<<26;
char pool[MEM],*pool_p=pool;

template<class T>
void alloc(T *&p,int sz){
	p=reinterpret_cast<T*>(pool_p);
	pool_p+=sz*sizeof(T);
	assert(pool_p<pool+MEM);
	F(i,0,sz)new(p+i)T();
}

template<class T>
struct Undo{
	T &x;
	T x0;
	Undo(T &x):x(x),x0(x){}
	~Undo(){x=x0;}
};

#define alloc_scope Undo<char*> _(pool_p)

template<class T>
struct Inf{};

template<>
struct Inf<i64>{
	static const i64 value=1LL<<40;
};

template<class T>
struct Max{
	T x;
	Max(T x=-Inf<T>::value):x(x){}
	Max<T> operator+(const Max<T> &w)const{return max(x,w.x);}
	void operator+=(const Max<T> &w){x=max(x,w.x);}
};

template<class T>
struct AddOp{
	T x;
	AddOp(T x=T()):x(x){}
	void operator*=(const AddOp<T> &w){x+=w.x;}
	friend void operator*=(Max<T> &x,const AddOp<T> &y){x.x+=y.x;}
};

template<class D,class M>
struct MSegTree{
	struct Node{
		D d;
		M m;
		void app(const M &t){
			d*=t;
			m*=t;
		}
		void up(const Node &a,const Node &b){
			d=a.d+b.d;
			d*=m;
		}
	}*tr;
	int mx;
	void alloc(int n){
		for(mx=1;mx<n+2;mx<<=1);
		::alloc(tr,mx*2);
	}
	Node &at(int x){
		return tr[mx+x];
	}
	D &operator[](int x){
		return tr[mx+x].d;
	}
	void range_update(int l,int r){
		l+=mx,r+=mx;
		for(l>>=1,r>>=1;l<r;l>>=1,r>>=1){
			Fe(x,l,r)up(x);
		}
		for(;l;l>>=1)up(l);
	}
	void up(int x){
		tr[x].up(tr[x*2],tr[x*2+1]);
	}
	void update(const M &t){
		tr[1].app(t);
	}
	void update_prefix(int x,const M &t){
		for(x+=mx+1;x>1;x>>=1,up(x)){
			if(x&1)tr[x-1].app(t);
		}
	}
	D query(){
		return tr[1].d;
	}
	void dn(int x){
		tr[x*2].app(tr[x].m);
		tr[x*2+1].app(tr[x].m);
		tr[x].m=M();
	}
	void dna(int x){
		x+=mx;
		for(int c=__builtin_ctz(mx);c>0;--c)dn(x>>c);
	}
	void dna(int l,int r){
		l+=mx,r+=mx;
		for(int c=__builtin_ctz(mx);c>0;--c){
			int L=l>>c,R=r>>c;
			Fe(i,L,R)dn(i);
		}
	}
};

int m;
struct Op{
	int x,y,id;
	int a[2][2];
	void R(int i){
		x=read(2,m);
		y=read(2,m);
		id=i;
		F(i,0,2)F(j,0,2)a[i][j]=read(1,maxv);
	}
}qs[M],qs2[M];

template<class T>
struct Array{
	T *v;
	int sz;
	Array(){}
	Array(int n){alloc(n);}
	void alloc(int n){
		sz=n;
		::alloc(v,n);
	}
	T &operator[](int x){
		return v[x];
	}
};

template<class T>
struct Grid{
	T *v;
	int xsz,ysz;
	Grid(){}
	Grid(int xn,int yn){
		alloc(xn,yn);
	}
	void alloc(int xn,int yn){
		xsz=xn;ysz=yn;
		::alloc(v,xn*yn);
	}
	T &operator()(int x,int y){
		return v[x*ysz+y];
	}
};

struct Des{
	int sz,x[M],id[M];
	void clr(){
		sz=0;
	}
	void ins(int a){
		x[sz++]=a;
	}
	void build(){
		ins(1),ins(m+1);
		std::sort(x,x+sz);
		sz=std::unique(x,x+sz)-x;
		F(i,1,sz)F(j,x[i-1],x[i])id[j]=i;
	}
}xs,ys;

struct NoD{
	char _[0];
	template<class T>
	void operator*=(const T &x){}
	friend NoD operator+(NoD a,NoD b){return NoD();}
};

template<class T>
struct HAddOp{
	T h,a,a1;
	bool commit;
	HAddOp(T x=0):a1(x),commit(0){}
	void operator*=(const HAddOp<T> &w){
		if(w.commit){
			if(commit){
				h=max(h,a+a1+w.h);
				a+=a1+w.a;
				a1=w.a1;
			}else{
				h=a1+w.h;
				a=a1+w.a;
				a1=w.a1;
				commit=1;
			}
		}else{
			a1+=w.a1;
		}
	}
};

MSegTree<Max<i64>,AddOp<i64>> tr[M];
MSegTree<NoD,HAddOp<i64>> tr0;

struct DC{
	Array<int> x,y;
	Grid<MSegTree<Max<i64>,AddOp<i64>>::Node> g;
	void set_sz(int sz){
		x.alloc(sz);
		y.alloc(sz);
	}
	void run(int m1){
		int sz=x.sz;
		if(sz==1){
			F(i,0,2)F(j,0,2){
				printf("%lld%c",g(i,j).d.x," \n"[i&j]);
				g(i,j).app(qs[m1].a[i][j]);
			}
			return;
		}
		int o=0;
		F(I,0,2){
			alloc_scope;
			int sz1=(I?sz-sz/2:sz/2);
			DC dc;
			dc.set_sz(sz1);
			Array<int> xe(g.xsz),ye(g.ysz);
			F(i,0,sz1){
				xe[x[o+i]]=1;
				ye[y[o+i]]=1;
			}
			xe[0]=ye[0]=0;
			F(i,1,xe.sz)xe[i]+=xe[i-1];
			F(i,1,ye.sz)ye[i]+=ye[i-1];
			F(i,0,sz1){
				dc.x[i]=xe[x[o+i]];
				dc.y[i]=ye[y[o+i]];
			}
			dc.g.alloc(xe[xe.sz-1]+1,ye[ye.sz-1]+1);
			F(i,0,g.xsz)F(j,0,g.ysz){
				dc.g(xe[i],ye[j]).d+=g(i,j).d;
			}
			dc.run(m1+o);
			if(!I)
			F(i,0,g.xsz)F(j,0,g.ysz){
				auto v=dc.g(xe[i],ye[j]).m;
				g(i,j).d*=v;
				g(i,j).m=v;
			}
			if(I)
			F(i,0,g.xsz)F(j,0,g.ysz){
				g(i,j).m*=dc.g(xe[i],ye[j]).m;
			}
			o+=sz1;
		}
	}
};

i64 v0[M],v1[M];
void cal(int m1,int m2){
	alloc_scope;
	
	xs.clr();
	ys.clr();
	F(i,m1,m2){
		Op &q=qs[i];
		xs.ins(q.x);
		ys.ins(q.y);
	}
	xs.build();
	ys.build();
	
	Grid<i64> g(xs.sz,ys.sz);
	F(i,1,ys.sz){
		int L=ys.x[i-1],R=ys.x[i];
		tr[i].alloc(R-L);
		F(j,L,R)tr[i][j-L+1]=v0[j];
		tr[i].range_update(1,R-L);
		g(0,i)=tr[i].query().x;
	}
	tr0.alloc(ys.sz);
	F(i,1,ys.sz)tr0.at(i).m=0;
	
	int p=0;
	F(i,1,xs.sz){
		int L=xs.x[i-1],R=xs.x[i];
		F(x,L,R){
			for(;p<m&&qs2[p].x==x;++p){
				Op &q=qs2[p];
				if(q.id>=m1)continue;
				int a1=q.a[1][0]-q.a[0][0];
				int a2=q.a[1][1]-q.a[0][1];
				a1-=a2;
				int w=ys.id[q.y],u=q.y+1-ys.x[w-1];
				
				i64 a=tr[w].query().x;
				tr[w].update_prefix(u-1,a1);
				a=tr[w].query().x-a;
				
				tr0.dna(w);
				auto &w0=tr0.at(w);
				w0.app(a);
				
				tr0.update_prefix(w-1,a1);
				tr0.update(a2);
			}
			HAddOp<i64> m;
			m.h=m.a=m.a1=0;
			m.commit=1;
			tr0.update(m);
		}
		tr0.dna(1,ys.sz);
		F(w,1,ys.sz){
			auto &w0=tr0.at(w).m;
			g(i,w)=g(0,w)+w0.h;
			g(0,w)+=w0.a;
			w0=0;
		}
	}
	
	int m0=m2-m1;
	DC dc;
	dc.set_sz(m0);
	dc.g.alloc(xs.sz-1,ys.sz-1);
	F(i,1,xs.sz)F(j,1,ys.sz)dc.g(i-1,j-1).d=g(i,j);
	F(i,0,m0){
		Op &q=qs[m1+i];
		dc.x[i]=xs.id[q.x]-1;
		dc.y[i]=ys.id[q.y]-1;
	}
	
	dc.run(m1);
	
	Fe(i,1,m)v1[i]=0;
	F(i,m1,m2){
		Op &q=qs[i];
		v1[1]+=q.a[0][0];
		v1[q.y]+=q.a[0][1]-q.a[0][0];
	}
	v0[1]+=v1[1];
	Fe(i,2,m)v1[i]+=v1[i-1],v0[i]+=v1[i];
}

int main(){
	//freopen( "1.in" , "r" , stdin );
	//freopen( "test.out" , "w" , stdout );
	m=read(1,maxm);
	F(i,0,m)qs[i].R(i);
	F(i,0,m)qs2[i]=qs[i];
	std::sort(qs2,qs2+m,[](const Op &a,const Op &b){return a.x<b.x;});
	int B=sqrt(m*4);
	for(int l=0,r;l<m;l=r){
		r=std::min(l+B,m);
		cal(l,r);
	}
	return 0;
}