P8818线段树写法

#include<bits/stdc++.h>
using namespace std;
const int M=1e6+10;
long long n,m,q,a[M],b[M];
struct node{
	long long l,r;
	long long maxn,minn;
	bool flag0;
	long long minbi,maxsm;//minbi最小的非负数，maxsm最大的负数
}treea[4*M],treeb[4*M];
void push_upa(long long idx){
	treea[idx].maxn = max (treea[idx*2].maxn,treea[idx*2+1].maxn);
	treea[idx].minn = min (treea[idx*2].minn,treea[idx*2+1].minn);
	treea[idx].minbi=min(treea[idx*2].minbi,treea[idx*2+1].minbi);
	treea[idx].maxsm=max(treea[idx*2].maxsm,treea[idx*2+1].maxsm);
	if(treea[idx*2].flag0||treea[idx*2+1].flag0) treea[idx].flag0=1;
	return ;
}
void push_upb(long long idx){
	treeb[idx].maxn=max(treeb[idx*2].maxn,treeb[idx*2+1].maxn);
	treeb[idx].minn=min(treeb[idx*2].minn,treeb[idx*2+1].minn);
	return ;
}
void builda(long long l,long long r,long long idx){
	treea[idx].l=l;treea[idx].r=r;treea[idx].flag0=0;
	if(l==r){
		treea[idx].maxn=a[l];
		treea[idx].minn=a[l];
		if(a[l]==0){
			treea[idx].flag0=1;
		}
		if(a[l]>=0){
			treea[idx].minbi=a[l];
			treea[idx].maxsm=LONG_LONG_MIN;
		}
		else{
			treea[idx].minbi=LONG_LONG_MAX;
			treea[idx].maxsm=a[l];
		}
		return ;
	}
	long long mid=(l+r)/2;
	builda(l,mid,idx*2);builda(mid+1,r,idx*2+1);
	push_upa(idx);
	return ;
}
void buildb(long long l,long long r,long long idx){
	treeb[idx].l=l;treeb[idx].r=r;
	if(l==r){
		treeb[idx].maxn=b[l];
		treeb[idx].minn=b[l];
		return ;
	}
	long long mid=(l+r)/2;
	buildb(l,mid,idx*2);buildb(mid+1,r,idx*2+1);
	push_upb(idx);
	return ;
}
long long checkamax(long long l,long long r,long long idx){
	if(treea[idx].r<l||r<treea[idx].l){return LONG_LONG_MIN;}
	if(l<=treea[idx].l&&treea[idx].r<=r){return treea[idx].maxn;}
	return max(checkamax(l,r,idx*2),checkamax(l,r,idx*2+1));
}
long long checkamin(long long l,long long r,long long idx){
	if(treea[idx].r<l||r<treea[idx].l){return LONG_LONG_MAX;}
	if(l<=treea[idx].l&&treea[idx].r<=r){return treea[idx].minn;}
	return min(checkamin(l,r,idx*2),checkamin(l,r,idx*2+1));
}
long long checkbmax(long long l,long long r,long long idx){
	if(treeb[idx].r<l||r<treeb[idx].l){return LONG_LONG_MIN;}
	if(l<=treeb[idx].l&&treeb[idx].r<=r){return treeb[idx].maxn;}
	return max(checkbmax(l,r,idx*2),checkbmax(l,r,idx*2+1));
}
long long checkbmin(long long l,long long r,long long idx){
	if(treeb[idx].r<l||r<treeb[idx].l){return LONG_LONG_MAX;}
	if(l<=treeb[idx].l&&treeb[idx].r<=r){return treeb[idx].minn;}
	return min(checkbmin(l,r,idx*2),checkbmin(l,r,idx*2+1));
}
long long checkamaxsm(long long l,long long r,long long idx){
	if(treea[idx].r<l||r<treea[idx].l){return LONG_LONG_MIN;}
	if(l<=treea[idx].l&&treea[idx].r<=r){return treea[idx].maxsm;}
	return max(checkamaxsm(l,r,idx*2),checkamaxsm(l,r,idx*2+1));
}
long long checkaminbi(long long l,long long r,long long idx){
	if(treea[idx].r<l||r<treea[idx].l){return LONG_LONG_MAX;}
	if(l<=treea[idx].l&&treea[idx].r<=r){return treea[idx].minbi;}
	return min(checkaminbi(l,r,idx*2),checkaminbi(l,r,idx*2+1));
}
bool check0(long long l,long long r,long long idx){
	if(treea[idx].r<l||r<treea[idx].l) return 0;
	if(l<=treea[idx].l&&treea[idx].r<=r){return treea[idx].flag0;}
	return (check0(l,r,idx*2)||check0(l,r,idx*2+1));
}
int main(){
	//freopen("game.in","r",stdin);
	//freopen("game.out","w",stdout);
	cin>>n>>m>>q;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=m;i++){
		cin>>b[i];
	}
	builda(1,n,1);
	buildb(1,m,1);
	while(q--){
		long long l1,l2,r1,r2;
		cin>>l1>>r1>>l2>>r2;
		long long amax=checkamax(l1,r1,1);
		long long amin=checkamin(l1,r1,1);
		long long bmin=checkbmin(l2,r2,1);
		long long bmax=checkbmax(l2,r2,1);
		long long amaxsm=checkamaxsm(l1,r1,1);
		long long aminbi=checkaminbi(l1,r1,1);
		if(l2==r2){
			bmax=b[l2];
			bmin=b[l2];
		}
		
		if(bmin>=0){
			if(amax>0){
				if(bmax==0){
					cout<<0<<endl;
				}
				else{
					cout<<amax*bmin<<endl;
				}
				continue;
			}
			if(amax<=0){
				if(amax==0){
					cout<<0<<endl;
				}
				else{
					cout<<amaxsm*bmax;
				}
				continue;
			}
		}
		else if(bmax<=0){
			if(amin<0){
				if(bmax==0){
					cout<<0<<endl;
				}
				else{
					cout<<amin*bmax<<endl;
				}
				continue;
			}
			else{
				if(amin==0){
					cout<<0<<endl;
				}
				else{
					cout<<amax*bmin<<endl;
				}
				continue;
			}
		}
		else{
			if(check0(l1,r1,1)){
				cout<<0<<endl;
				continue;
			}
			else if(amax<0){
				cout<<amaxsm*bmax<<endl;
				continue;
			}
			else if(amin>0){
				cout<<amin*bmin<<endl;
				continue;
			}
			else{
				//max(先手最大负数×后手最大正数,先手最小正数×后手最小负数)
				cout<<max(amaxsm*bmax,aminbi*bmin)<<endl;
				continue;
			}
		}
	}
	return 0;
}