https://www.luogu.com.cn/problem/P8818

#include <bits/stdc++.h>
using namespace std;

int n,m,q;
int a[100010],b[100010];
int mxf[100010][18],mxq[100010][18],miq[100010][18],mif[100010][18];
int mx[100010][18],mi[100010][18],lg[100010];
int main()
{
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		mxq[i][0]=a[i];
		if(a[i]>=0) mxf[i][0]=-(int)1e9;
		else mxf[i][0]=a[i];
		miq[i][0]=a[i];
		if(a[i]<0) mif[i][0]=(int)1e9;
		else mif[i][0]=a[i];
	}
	for(int i=1;i<=m;i++)
	{
		scanf("%d",&b[i]);
		mx[i][0]=b[i];
		mi[i][0]=b[i];
	}
	lg[0]=-1;
	for(int i=1;i<=100000;i++)  lg[i]=lg[i>>1]+1;
	for(int j=1;j<=17;j++)
	{
		int lim=n-(1<<j)+1;
		for(int i=1;i<=lim;i++)
		{
			mxq[i][j]=max(mxq[i][j-1],mxq[i+(1<<(j-1))][j-1]);
			miq[i][j]=min(miq[i][j-1],miq[i+(1<<(j-1))][j-1]);
			mif[i][j]=min(mif[i][j-1],mif[i+(1<<(j-1))][j-1]);
			mxf[i][j]=max(mxf[i][j-1],mxf[i+(1<<(j-1))][j-1]);
		}
	}
	for(int j=1;j<=17;j++)
	{
		int lim=m-(1<<j)+1;
		for(int i=1;i<=lim;i++)
		{
			mx[i][j]=max(mx[i][j-1],mx[i+(1<<(j-1))][j-1]);
			mi[i][j]=min(mi[i][j-1],mi[i+(1<<(j-1))][j-1]);
		}
	}
	while(q--)
	{
		int l1,r1,l2,r2;
		scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
		int l=lg[r1-l1+1];
		int x=max(mxq[l1][l],mxq[r1-(1<<l)+1][l]);
		int y=max(mxf[l1][l],mxq[r1-(1<<l)+1][l]);
		int z=min(miq[l1][l],miq[r1-(1<<l)+1][l]);
		int h=min(mif[l1][l],mif[r1-(1<<l)+1][l]);
		l=lg[r2-l2+1];
		int xx=max(mx[l2][l],mx[r2-(1<<l)+1][l]);
		int yy=min(mi[l2][l],mi[r2-(1<<l)+1][l]);
		int ans=(int)-1e9;
		if(x>=0) ans=max(ans,x*yy);
		if(h!=(int)1e9) ans=max(ans,h*yy);
		if(y<0) ans=max(ans,y*xx);
		if(z<0) ans=max(ans,z*xx);
		printf("%d\n",ans);
	}
}