暴力解法（60分）

设矩阵( c[i][j] = a[i] \times b[j] )，每轮游戏的得分为：( l1 )行至( r1 )行中每行的( l2 )至( r2 )列的最小值中的最大值。即先对每行在([l2, r2])列中求最小值，再取这些最小值的最大值作为答案。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e5+100;
const LL INF=1e18+1;
LL a[N], b[N];
int main()
{
    int n, m, q;scanf("%d%d%d", &n, &m, &q);
    for(int i=1;i<=n;i++) scanf("%lld", &a[i]);
    for(int i=1;i<=m;i++) scanf("%lld", &b[i]);
    while(q--)
    {
        int l1, r1, l2, r2;scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
        LL ans=-INF;
        for(int i=l1;i<=r1;i++)
        {
            LL tmin=INF;
            for(int j=l2;j<=r2;j++) tmin=min(tmin, a[i]*b[j]);
            ans=max(ans, tmin);
        }
        printf("%lld\n", ans);
    }
    return 0;
}

标称解法

每轮游戏的得分为( l1 )至( r1 )行中每行的( l2 )至( r2 )列的最小值中的最大值，即( a_i \times b_j )的四种情况：最小负数(mnf)、最大负数(mxf)、最小正数(mnz)、最大正数(mxz)。通过线段树分别维护( a )数组和( b )数组的这四种值，查询时获取( a )的四种值和( b )的四种值，计算所有组合的最小值，取最大值作为答案。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define lc(p) (p<<1)
#define rc(p) (p<<1|1)
const int N=1e5+10;
const LL INF=1e18+1;
struct node
{
    LL mnf, mxf, mnz, mxz;
    /*每轮游戏的得分为：l1至r1行中每行的l2至r2的最小值中的最大值 ai*aj。
    ai和aj为以下四种情况之一：
    1、mnf:最小负数
    2、mxf:最大负数
    3、mnz:最小正数
    4、mxz:最大正数
    */
}tra[N<<2], trb[N<<2];LL a[2][N];

void pushup(node tr[], int p)
{
    tr[p].mnf=min(tr[lc(p)].mnf, tr[rc(p)].mnf);
    tr[p].mxf=max(tr[lc(p)].mxf, tr[rc(p)].mxf);
    tr[p].mnz=min(tr[lc(p)].mnz, tr[rc(p)].mnz);
    tr[p].mxz=max(tr[lc(p)].mxz, tr[rc(p)].mxz); 
}
void bt(node tr[], int p, int l, int r, int k)
{
    tr[p]=node{INF, -INF, INF, -INF};
    if(l==r) 
    {
        if(a[k][l]>=0)tr[p]=node{INF, -INF, a[k][l], a[k][l]}; 
        else          tr[p]=node{a[k][l], a[k][l], INF, -INF}; 
        return ;
    }
    int m=(l+r)>>1;
    bt(tr, lc(p), l,  m, k);
    bt(tr, rc(p), m+1, r, k);
    pushup(tr, p);
}
node query(node tr[], int p, int l, int r, int x, int y)
{
    if(x<=l && r<=y) return tr[p];
    node ans=node{INF, -INF, INF, -INF};
    int m=(l+r)>>1;
    if(x<=m)
    {
        node tmp=query(tr, lc(p), l, m, x, y);
        ans.mnf=min(ans.mnf, tmp.mnf);
        ans.mxf=max(ans.mxf, tmp.mxf);
        ans.mnz=min(ans.mnz, tmp.mnz);
        ans.mxz=max(ans.mxz, tmp.mxz);
    }
    if(y>m)
    {
        node tmp=query(tr, rc(p), m+1, r, x, y);
        ans.mnf=min(ans.mnf, tmp.mnf);
        ans.mxf=max(ans.mxf, tmp.mxf);
        ans.mnz=min(ans.mnz, tmp.mnz);
        ans.mxz=max(ans.mxz, tmp.mxz);
    }
    return ans;
}
void copy(LL t[], node no) {t[1]=no.mnf;t[2]=no.mxf;t[3]=no.mnz;t[4]=no.mxz;}
int main()
{
    freopen("a.in", "r", stdin);
    int n, m, q;scanf("%d%d%d", &n, &m, &q);
    for(int i=1;i<=n;i++) scanf("%lld", &a[0][i]);
    for(int i=1;i<=m;i++) scanf("%lld", &a[1][i]);
    bt(tra, 1, 1, n, 0);
    bt(trb, 1, 1, m, 1);
    while(q--) {
        int l1, r1, l2, r2;scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
        node x=query(tra, 1, 1, n, l1, r1);
        node y=query(trb, 1, 1, m, l2, r2);LL na[5], nb[5];
        copy(na, x);copy(nb, y);LL ans=-INF;for(int i=1;i<=4;i++)
            for(int j=1;j<=4;j++) {
                if(na[i]==INF||na[i]==-INF||nb[j]==INF||nb[j]==-INF) continue;LL t=na[i]*nb[j];
                ans=max(ans, t);
            }
        printf("%lld\n", ans);
    } 
    return 0;
}

暴力60分：

/*
设矩阵c[i][j]=a[i]*b[j]
每轮游戏的得分为：
l1行中第l2至r2的最小值t[l1]=min(c[l1][l2],c[l1][l2+1],...,c[l1][r2])
...
r1行中第l2至r2的最小值t[r1]=min(c[r1][l2],c[r1][l2+1],...,c[r1][r2]) 
答案就是：max(t[l1],...,t[r1])
*/
#include<bits/stdc++.h>//暴力程序60分，还是很有性价比的
using namespace std;
typedef long long LL;
const int N=1e5+100;
const LL INF=1e18+1;
LL a[N],b[N];
int main()
{
    int n,m,q;scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    for(int i=1;i<=m;i++) scanf("%lld",&b[i]);
    while(q--)
    {
        int l1,r1,l2,r2;scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
        LL ans=-INF;
        for(int i=l1;i<=r1;i++)
        {
            LL tmin=INF;
            for(int j=l2;j<=r2;j++) tmin=min(tmin,a[i]*b[j]);
            ans=max(ans,tmin);
        }
        printf("%lld\n",ans);
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define lc(p) (p<<1)
#define rc(p) (p<<1|1)
const int N=1e5+10;
const LL INF=1e18+1;
struct node
{
    LL mnf,mxf,mnz,mxz;
/*每轮游戏的得分为：l1至r1行中每行的l2至r2的最小值中的最大值 ai*aj。
ai和aj为以下四种情况之一：
1、mnf:最小负数
2、mxf:最大负数
3、mnz:最小正数
4、mxz:最大正数
*/
}tra[N<<2],trb[N<<2];LL a[2][N];
void pushup(node tr[],int p)
{
tr[p].mnf=min(tr[lc(p)].mnf,tr[rc(p)].mnf);
tr[p].mxf=max(tr[lc(p)].mxf,tr[rc(p)].mxf);
tr[p].mnz=min(tr[lc(p)].mnz,tr[rc(p)].mnz);
tr[p].mxz=max(tr[lc(p)].mxz,tr[rc(p)].mxz);
}
void bt(node tr[],int p,int l,int r,int k)
{
tr[p]=node{INF,-INF,INF,-INF};
if(l==r)
{
if(a[k][l]>=0)tr[p]=node{INF,-INF,a[k][l],a[k][l]};
else          tr[p]=node{a[k][l],a[k][l],INF,-INF};
return ;
}
int m=(l+r)>>1;
bt(tr,lc(p),l,  m,k);
bt(tr,rc(p),m+1,r,k);
pushup(tr,p);
}
node query(node tr[N],int p,int l,int r,int x,int y)
{
if(x<=l && r<=y) return tr[p];
node ans=node{INF,-INF,INF,-INF};
int m=(l+r)>>1;
if(x<=m)
{
node tmp=query(tr,lc(p),l,m,x,y);
ans.mnf=min(ans.mnf,tmp.mnf);
ans.mxf=max(ans.mxf,tmp.mxf);
ans.mnz=min(ans.mnz,tmp.mnz);
ans.mxz=max(ans.mxz,tmp.mxz);
}
if(y>m)
{
node tmp=query(tr,rc(p),m+1,r,x,y);
ans.mnf=min(ans.mnf,tmp.mnf);
ans.mxf=max(ans.mxf,tmp.mxf);
ans.mnz=min(ans.mnz,tmp.mnz);
ans.mxz=max(ans.mxz,tmp.mxz);
}
return ans;
}
void copy(LL t[],node no) {t[1]=no.mnf;t[2]=no.mxf;t[3]=no.mnz;t[4]=no.mxz;}
int main()
{
freopen("a.in","r",stdin);
int n,m,q;scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=n;i++) scanf("%lld",&a[0][i]);
for(int i=1;i<=m;i++) scanf("%lld",&a[1][i]);
bt(tra,1,1,n,0);
bt(trb,1,1,m,1);
while(q--)
{
int l1,r1,l2,r2;scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
node x=query(tra,1,1,n,l1,r1);
node y=query(trb,1,1,m,l2,r2);
LL na[5],nb[5];
copy(na,x);
copy(nb,y);
LL ans=-INF;
for(int i=1;i<=4;i++) {
LL tmin=INF;
if(na[i]INF||na[i]-INF) continue;
for(int j=1;j<=4;j++) {
if(nb[j]INF||nb[j]-INF) continue;
tmin=min(tmin,na[i]*nb[j]);
}
ans=max(ans,tmin);
}
printf("%lld\n",ans);
}
return 0;
}