题目传送门
闲聊：本蒟蒻调了两天……
（以下称先手为A，后手为B）
首先\(c\)矩阵就是个诈骗的障眼法，真正的题面应该是这样：
给你两个固定的数组\(a\)、\(b\)，每次询问给你\(l1\)、\(l2\)、\(r1\)、\(r2\)，A要先选一个数，这个数在\(a\)数组中，且这个数对应的下标在\([l1,r1]\)范围里。B后选一个\(b\)数组中的数，同样，这个数对应的下表在\([l2,r2]\)范围里。
设A选的数是\(x\)，B选的数是\(y\)，则最终结果是\(x \times y\)。A要让结果最大，B要让结果最小，求最终结果会是什么。
首先，由于\(a\)、\(b\)数组里的数有正有负，符号会影响两人最终的决策，所以我们不妨比较笨地分讨一下。
1.如果\(b\)的选定区间里全是非负数：
①如果此时\(a\)的选定区间里全是负数，那么B知道A会选负数，B为了让值尽可能小，一定会选最大的非负数。那么A思考后知道B会选最大的非负数，A为了让最终结果最大，必然选择绝对值最小的负数（也就是\(a\)中的最大值）。
②如果\(a\)的选定区间中有非负数，那么A首先一定会选非负数（为了让结果非负） ，B思考到这一层后（即A会选非负数），为了让结果最小一定会选最小的非负数（或者说，\(b\)选定区间中的最小值）。A的话知道B选非负数，那么为了让结果最大，他会选择\(a\)选定区间中的最大非负数（即最大值）。
2.如果\(b\)的选定区间里全是负数：
③如果此时\(a\)的选定区间里全是非负数，类似①，B会选绝对值最大的负数（最小的负数），A预判了B的预判，A会选最小的非负数（也就是\(a\)选定区间中的最小值）。
④如果\(a\)的选定区间中有负数，那么类似②，B知道A会选负数，B会选一个绝对值最小的负数（也就是\(b\)选定区间中的最大值），A思考B的思考后，会选择绝对值最大的负数（也就是\(a\)选定区间中的最小值）。
3.如果\(b\)的选定区间里两种都有：
⑤如果\(a\)选定区间中全部为非负数，首先B一定不会选非负数（防止结果非负），这样问题就转化为了③的那种情景，B选最小值，A选最小值。
⑥如果\(a\)选定区间中全部为负数，那么类似⑤，B一定不会选负数（这样结果就大于0了），问题转化为①，B选最大值，A选最大值。
⑦如果\(a\)也是两种都有，那么A有两种决策：一种是选非负数，那么B就会选负数，同③，B选最小值，A选最小的非负数（注意A要在非负数里选一个）。另一种是选负数，那么B就会选负数，同①，B选最大值，A选最大的负数。
这样，由于\(a\)、\(b\)都是静态数组，我们用六个ST表维护六个值：\(a\)数组区间最大最小值、\(a\)数组区间非负数区间最小值、\(a\)数组负数区间最大值、以及\(b\)数组区间最大最小值。
至于如何维护\(a\)数组区间非负数区间最小值和\(a\)数组负数区间最大值，我们新开两个数组（以下称\(a1\)、\(a2\)），\(a1\)数组在\(a\)数组的基础上，把所有负数修改为一个极大值，同理\(a2\)数组在\(a\)数组的基础上把所有非负数修改为一个极小值。然后正常使用ST表求最值即可。
时间复杂度\(O(nlogn+q)\)。
理论上本题还可以使用线段树维护区间最值，这里我采用的是ST表，只贴ST表代码。
P8818_ST表
#include<bits/stdc++.h>
#define int long long
using namespace std;inline int read(){int x=0,f=1;char c=getchar();while(c<48){if(c=='-') f=-1;c=getchar();} while(c>47) x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f;
}const int N=1e5+5;
const int inf=2e18;//极大值一定要往大里赋，否则过不了sub1
int n,m,q,a[N],b[N],a1[N],a2[N],f[6][21][N];
//f[0][...][...]:a数组区间最大值
//f[1][...][...]:a数组区间最小值
//f[2][...][...]:a数组非负数区间最小值
//f[3][...][...]:a数组负数区间最大值
//f[4][...][...]:b数组区间最大值
//f[5][...][...]:b数组区间最小值 inline void init(){//初始化 for(int i=1;i<=n;i++){f[0][0][i]=a[i],f[1][0][i]=a[i];f[2][0][i]=a1[i],f[3][0][i]=a2[i];}for(int i=1;i<=m;i++){f[4][0][i]=f[5][0][i]=b[i];}//ST表求值 for(int i=1;i<=20;i++){for(int j=1;j+(1<<i)-1<=n;j++){f[0][i][j]=max(f[0][i-1][j],f[0][i-1][j+(1<<(i-1))]);f[1][i][j]=min(f[1][i-1][j],f[1][i-1][j+(1<<(i-1))]);f[2][i][j]=min(f[2][i-1][j],f[2][i-1][j+(1<<(i-1))]);f[3][i][j]=max(f[3][i-1][j],f[3][i-1][j+(1<<(i-1))]);f[4][i][j]=max(f[4][i-1][j],f[4][i-1][j+(1<<(i-1))]);f[5][i][j]=min(f[5][i-1][j],f[5][i-1][j+(1<<(i-1))]);}}
}signed main(){n=read(),m=read(),q=read();//a1、a2数组定义同题解 for(int i=1;i<=n;i++){a[i]=read();//a1、a2数组初始化 if(a[i]>=0){a2[i]=-inf,a1[i]=a[i];}else{a2[i]=a[i],a1[i]=inf;}}for(int i=1;i<=m;i++){b[i]=read();}init();for(int i=1;i<=q;i++){int l1=read(),r1=read(),l2=read(),r2=read();int ln1=log(r1-l1+1)/log(2),ln2=log(r2-l2+1)/log(2);int c1,c2,c3,c4,c5,c6,ans=-inf;c1=max(f[0][ln1][l1],f[0][ln1][r1-(1<<ln1)+1]);//amaxc2=min(f[2][ln1][l1],f[2][ln1][r1-(1<<ln1)+1]);//a1minc3=max(f[3][ln1][l1],f[3][ln1][r1-(1<<ln1)+1]);//a2maxc4=min(f[1][ln1][l1],f[1][ln1][r1-(1<<ln1)+1]);//aminc5=max(f[4][ln2][l2],f[4][ln2][r2-(1<<ln2)+1]);//bmaxc6=min(f[5][ln2][l2],f[5][ln2][r2-(1<<ln2)+1]);//bmin//c1:a数组区间最大值//c2:a数组非负数区间最小值//c3:a数组负数区间最大值//c4:a数组区间最小值//c5:b数组区间最大值//c6:b数组区间最小值if(c6>=0){if(c1<0){//case1ans=max(ans,c1*c5); }else{//case2ans=max(ans,c6*c1);}}else if(c5<0){if(c4>=0){//case3ans=max(ans,c6*c4);}else{//case4ans=max(ans,c5*c4);}}else{if(c4>=0){//case5ans=max(ans,c6*c4);}else if(c1<0){//case6ans=max(ans,c5*c1);}else{ans=max(ans,max(c6*c2,c5*c3));//case7}}printf("%lld\n",ans);}return 0;
}