有点长，开了6个ST表

#include <bits/stdc++.h>
using namespace std;
long long n,m,q,a[100010],b[100010],fsn[100010][20],fbn[100010][20],fzn[100010][20],ffn[100010][20],fsm[100010][20],fbm[100010][20];
inline long long read()
{
	long long 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;
}

int main()
{
    n=read();m=read();q=read();
    for(int i=0;i<n;i++)
        {
	    a[i]=read();
	    fsn[i][0]=a[i];
	    fbn[i][0]=a[i];
	    if(a[i]>=0)fzn[i][0]=a[i];
	    else fzn[i][0]=99999999;
	    if(a[i]<=0)ffn[i][0]=a[i];
	    else ffn[i][0]=-99999999;
	    }
    for(int i=0;i<m;i++)
        {
	    b[i]=read();
	    fsm[i][0]=b[i];
	    fbm[i][0]=b[i];
	    }
	for(int j=1;j<20;j++)
	     for(int i=0;i+(1<<(j-1))<n;i++)
	         {
	         	fsn[i][j]=min(fsn[i][j-1],fsn[i+(1<<(j-1))][j-1]);
	         	fbn[i][j]=max(fbn[i][j-1],fbn[i+(1<<(j-1))][j-1]);
                fzn[i][j]=min(fzn[i][j-1],fzn[i+(1<<(j-1))][j-1]);
                ffn[i][j]=max(ffn[i][j-1],ffn[i+(1<<(j-1))][j-1]);
			 }
	for(int j=1;j<20;j++)
	    for(int i=0;i+(1<<(j-1))<m;i++)
	         {
	         	fsm[i][j]=min(fsm[i][j-1],fsm[i+(1<<(j-1))][j-1]);
	         	fbm[i][j]=max(fbm[i][j-1],fbm[i+(1<<(j-1))][j-1]);
			 }
	for(int i=0;i<q;i++)
	    {
	    	long long sn=read()-1,tn=read()-1,sm=read()-1,tm=read()-1;
	    	long long kn=log2(tn-sn+1),km=log2(tm-sm+1);
	    	long long ns=min(fsn[sn][kn],fsn[tn-(1<<kn)+1][kn]),nb=max(fbn[sn][kn],fbn[tn-(1<<kn)+1][kn]),nz=min(fzn[sn][kn],fzn[tn-(1<<kn)+1][kn]),nf=max(ffn[sn][kn],ffn[tn-(1<<kn)+1][kn]);
	    	long long ms=min(fsm[sm][km],fsm[tm-(1<<km)+1][km]),mb=max(fbm[sm][km],fbm[tm-(1<<km)+1][km]);
	    	if(ms<=0&&mb<=0)
	    	   {
	    	   	if(ns>0)printf("%lld\n",ns*mb);
	    	   	else printf("%lld\n",ns*mb);
			   }
			else if(ms>=0&&mb>=0)
			   {
	    	   	if(nb>0)printf("%lld\n",nb*ms);
	    	   	else printf("%lld\n",nb*ms);
			   }
			else if(ms<=0&&mb>=0)
			   {
			   	if(nf==-99999999)
			   	     {
					  printf("%lld\n",ns*ms);	
					  continue;
					 }
				if(nz==99999999)
				     {
					  printf("%lld\n",nb*mb);	
					  continue;
					 }
			   	long long z=nz+nf;
				if(z>0)printf("%lld\n",nf*mb);	
				else if(z<0)printf("%lld\n",nz*ms);	
		    	else
		    	    {
		    	    if(fabs(ms)>fabs(mb))printf("%lld\n",-(long long)(fabs(mb)*fabs(nz)));
			   	    else printf("%lld\n",-(long long)(fabs(ms)*fabs(nz)));
					}
			   }
		}
	return 0;
}

提交记录