85pts!玄关求条

#include<bits/stdc++.h>
#define int long long
#define inf (int)(1e14)
using namespace std;
int n,m,q;
int a[100086];
int b[100086];
int f[10][100086][30];
int al,ar,bl,br;
int ak,bk;
int amx,amn,bmx,bmn,_amx,_amn,_bmx,_bmn,a_0,b_0;
int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
signed main(){
//	freopen("a.txt","r",stdin);
	n=read();m=read();q=read();
	for(int i=1;i<=n;i++){
		a[i]=read();
	}
	for(int i=1;i<=m;i++){
		b[i]=read();
	}
	for(int i=1;i<=n;i++){
		f[0][i][0]=f[3][i][0]=a[i];
		f[1][i][0]=(a[i]>=0?a[i]:LLONG_MAX);
		f[2][i][0]=(a[i]<0?a[i]:LLONG_MIN);
		if(a[i]==0)f[4][i][0]=1;
	}
	for(int i=1;i<=m;i++){
		f[5][i][0]=f[8][i][0]=b[i];
		f[6][i][0]=(b[i]>=0?b[i]:LLONG_MAX);
		f[7][i][0]=(b[i]<0?b[i]:LLONG_MIN);
		if(b[i]==0)f[9][i][0]=1;
	}
	for(int j=1;j<=log2(n);j++){
		for(int i=1;i<=n;i++){
			if(i+(1<<(j-1))<=n){
				f[0][i][j]=max(f[0][i][j-1],f[0][i+(1<<(j-1))][j-1]);
				f[1][i][j]=min(f[1][i][j-1],f[1][i+(1<<(j-1))][j-1]);
				f[2][i][j]=max(f[2][i][j-1],f[2][i+(1<<(j-1))][j-1]);
				f[3][i][j]=min(f[3][i][j-1],f[3][i+(1<<(j-1))][j-1]);
				f[4][i][j]=max(f[4][i][j-1],f[4][i+(1<<(j-1))][j-1]);
			}
		}
	}
	for(int j=1;j<=log2(n);j++){
		for(int i=1;i<=m;i++){
			if(i+(1<<(j-1))<=m){
				f[5][i][j]=max(f[5][i][j-1],f[5][i+(1<<(j-1))][j-1]);
				f[6][i][j]=min(f[6][i][j-1],f[6][i+(1<<(j-1))][j-1]);
				f[7][i][j]=max(f[7][i][j-1],f[7][i+(1<<(j-1))][j-1]);
				f[8][i][j]=min(f[8][i][j-1],f[8][i+(1<<(j-1))][j-1]);
				f[9][i][j]=max(f[9][i][j-1],f[9][i+(1<<(j-1))][j-1]);
			}
		}
	}
	while(q--){
		cin>>al>>ar>>bl>>br;
		ak=log2(ar-al+1),bk=log2(br-bl+1);
		amx=max(f[0][al][ak],f[0][ar-(1<<ak)+1][ak]);
		amn=min(f[1][al][ak],f[1][ar-(1<<ak)+1][ak]);
		_amx=max(f[2][al][ak],f[2][ar-(1<<ak)+1][ak]);
		_amn=min(f[3][al][ak],f[3][ar-(1<<ak)+1][ak]);
		a_0=max(f[4][al][ak],f[4][ar-(1<<ak)+1][ak]);
		bmx=max(f[5][bl][bk],f[5][br-(1<<bk)+1][bk]);
		bmn=min(f[6][bl][bk],f[6][br-(1<<bk)+1][bk]);
		_bmx=max(f[7][bl][bk],f[7][br-(1<<bk)+1][bk]);
		_bmn=min(f[8][bl][bk],f[8][br-(1<<bk)+1][bk]);
		b_0=max(f[9][bl][bk],f[9][br-(1<<bk)+1][bk]);
		int ans;
		if(_amn>=0){
			if(_bmn>=0){
				ans=amx*_bmn;
			}
			else if(bmx<0){
				ans=_amn*_bmn;
			}
			else{
				ans=_amn*_bmn;
			}
		}
		else if(amx<0){
			if(_bmn>=0){
				ans=amx*bmx;
			}
			else if(bmx<0){
				ans=_amn*bmx;
			}
			else{
				ans=amx*bmx;
			}
		}
		else{
			if(_bmn>=0){
				ans=amx*_bmn;
			}
			else if(bmx<0){
				ans=_amn*bmx;
			}
			else{
				ans=max(_amx*bmx,amn*_bmn);
			}
		}
		if(a_0)ans=max(ans,0ll);
		if(b_0)ans=min(0ll,ans);
		cout<<ans<<endl;
	}
	return 0;
}