【正经题解】策略游戏

给定两个区间，先手在 $A$ 序列给定区间内选择一个数，后手在 $B$ 序列给定区间内选另一个数。两人所选数字乘积为得分。先手希望得分尽量大，后手希望得分尽量小。
因为不存在相乘正负性改变的问题。由双方策略可知，先手必然选择区间内最大值，后手必然选择区间内最小值。因此使用线段树/ST表维护区间内最大值和最小值即可。
若先手操作区间长度为 1，则有如下几种情况：

1. 先手必须选的数是 0，此时答案是 0。
2. 先手必须选的数是正数，此时后手策略为选择其区间内的最小数。
3. 先手必须选的数是负数，此时后手策略为选择其区间内的最大数。

后手同理：

1. 后手必须选的数是 $0$，此时答案是 $0$。
2. 后手必须选的数是正数，此时先手策略为选择其区间内的最大数。
3. 后手必须选的数是负数，此时后手策略为选择其区间内的最小数。

此时双方的操作区间内都有多个数，其中双方的最优策略会使相乘的正负号改变。因此，我们应该按照双方操作区间内的正负数存在情况进行讨论。

我的做法将所有情况分为八类。以下的“最小”“最大”均指数本身的值而不是绝对值。

假设 $n,m$ 同级，使用线段树的时间复杂度为$O(n+qlogn)$，ST表的时间复杂度为 $O(nlogn+q)$，均可通过本题。

#include <cstdio>
#define max(a,b) (((a)>(b))?(a):(b))
#define min(a,b) (((a)<(b))?(a):(b))
#define ls(p) ((p)<<1)
#define rs(p) (((p)<<1)|1)
const int Nx=100010;
int N,M,Q,A[Nx],B[Nx];
struct node{long long maz,miz,maf,mif,zro;};
node As[4*Nx],Bs[4*Nx];
void pushnode(node &a,int val)
{
	if(val==0)
		a.zro=1;
	else if(val>0)
		a.maz=a.miz=val;
	else if(val<0)
		a.maf=a.mif=val;
}
node merge(node x,node y)
{
	node ret;
	ret.zro=x.zro||y.zro;
	if(!x.maz||!y.maz)
	{
		ret.maz=x.maz+y.maz;
		ret.miz=x.miz+y.miz;
	}
	else
	{
		ret.maz=max(x.maz,y.maz);
		ret.miz=min(x.miz,y.miz);
	}
	if(!x.maf||!y.maf)
	{
		ret.maf=x.maf+y.maf;
		ret.mif=x.mif+y.mif;
	}
	else
	{
		ret.maf=max(x.maf,y.maf);
		ret.mif=min(x.mif,y.mif);
	}
	return ret;
}
void build(int ll,int rr,int p,node seg[],int C[])
{
	if(ll==rr)
	{
		pushnode(seg[p],C[ll]);
		return;
	}
	int mid=(ll+rr)>>1;
	build(ll,mid,ls(p),seg,C);
	build(mid+1,rr,rs(p),seg,C);
	seg[p]=merge(seg[ls(p)],seg[rs(p)]);
}
node query(int ll,int rr,int p,int L,int R,node seg[])
{
	if(L<=ll&&rr<=R)
		return seg[p];
	int mid=(ll+rr)>>1;
	if(L>mid)
		return query(mid+1,rr,rs(p),L,R,seg);
	if(R<=mid)
		return query(ll,mid,ls(p),L,R,seg);
	return merge(query(ll,mid,ls(p),L,R,seg),query(mid+1,rr,rs(p),L,R,seg));
}
long long get_ans(node ax,node bx)
{
	long long ret;
	//printf("%d %d %d %d %d   %d %d %d %d %d\n",ax.maz,ax.miz,ax.maf,ax.mif,ax.zro,bx.maz,bx.miz,bx.maf,bx.mif,bx.zro);
	if(bx.mif!=0&&bx.miz==0)//后手无正数
	{
		if(ax.mif!=0)//先手有负数
			ret=(bx.zro)?0:ax.mif*bx.maf;
		else//先手无负数
			ret=(ax.zro)?0:ax.miz*bx.mif;
	}
	else if(bx.mif==0&&bx.miz!=0)//后手无负数
	{
		if(ax.miz!=0)//先手有正数
			ret=(bx.zro)?0:ax.maz*bx.miz;
		else//先手无正数
			ret=(ax.zro)?0:ax.maf*bx.maz;
	}
	else//后手正负都有/后手只有0
	{
		if(ax.zro)
			ret=0;
		else if(ax.mif!=0&&ax.miz==0)//先手无正数
			ret=ax.maf*bx.maz;
		else if(ax.mif==0&&ax.miz!=0)//先手无负数
			ret=ax.miz*bx.mif;
		else//先手正负都有
			ret=max(ax.miz*bx.mif,ax.maf*bx.maz);
	}
	return ret;
}
int main()
{
	scanf("%d%d%d",&N,&M,&Q);
	int i,j,k,la,ra,lb,rb;
	for(i=1;i<=N;i++)
		scanf("%d",&A[i]);
	for(i=1;i<=M;i++)
		scanf("%d",&B[i]);
	build(1,N,1,As,A);
	build(1,M,1,Bs,B);
	node ax,bx;
	while(Q--)
	{
		scanf("%d%d%d%d",&la,&ra,&lb,&rb);
		ax=query(1,N,1,la,ra,As);
		bx=query(1,M,1,lb,rb,Bs);
		printf("%lld\n",get_ans(ax,bx));
	}
}