上XP04讲的（写死我了）

---

这道题是一个博弈论中的极大极小模型：
·小L想最大化得分（他先选一个A[x]）
·小Q想最小化得分（他随后选一个B[y]）
·得分为A[x]*B[y]，最终得分是小L选择的A[x]对应的最坏情况的最优解

---

解题思路

我们可以将这个问题建模为：
1.对于某个固定的A[x],小Q会选择一个B[y]使得A[x]*b[y]最小
2.那么对小L而言，他要在a[l1...r1]中选择一个x，使得对应的最坏情况尽量好
问题可以转化为：
对每个候选的A[x]：
1.如果A[x]>=0，则A[x]*B[y]最小当B[y]取最小
2.如果A[x]<0，则A[x]B[y]最小当B[y]取最大
所以每个A[x]的最坏得分=A[x](A[x]>=0?min(B[l2..r2]):max(B[l2...r2]))
然后再取其中最大值

直接枚举会超时所以用ST表

时间复杂度：
·预处理：O((n+m)log n)
·每次查询：O(1)

#include<iostream>
#include<limits.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
const int logN=__lg(N);//log2(n),用于ST表
int a[N],b[N];
struct STMAX{
    int f[N][logN+1];
    void init(int n){
        for(int j=1;j<=logN;j++){
            int p=(1<<(j-1));
            for(int i=1;i+p-1<=n;i++)
                f[i][j]=max(f[i][j-1],f[i+p][j-1]);
        }
    }
    int query(int l,int r){
        int s=__lg(r-l+1);
        return max(f[l][s],f[r-(1<<s)+1][s]);
    }
};//区间最大值
struct STMIN{
    int f[N][logN+1];
    void init(int n){
        for(int j=1;j<=logN;j++){
            int p=(1<<(j-1));
            for(int i=1;i+p-1<=n;i++)
                f[i][j]=min(f[i][j-1],f[i+p][j-1]);
        }
    }
    int query(int l,int r){
        int s=__lg(r-l+1);
        return min(f[l][s],f[r-(1<<s)+1][s]);
    }
};//区间最小值
STMAX aMax,anegMax,bMax;//a最大值，a负数最大值，b最小值
STMIN aMin,aposMin,bMin;//a最小值，a负数最小值，b最小值
int main(){
    int n,m,q;
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=m;i++)cin>>b[i];
    for(int i=1;i<=n;i++)aMax.f[i][0]=a[i];
    aMax.init(n);
    for(int i=1;i<=n;i++)aMin.f[i][0]=a[i];
    aMin.init(n);
    for(int i=1;i<=n;i++)anegMax.f[i][0]=(a[i]>=0)?-2e9:a[i];
    anegMax.init(n);
    for(int i=1;i<=n;i++)aposMin.f[i][0]=(a[i]>=0)?a[i]:2e9;
    aposMin.init(n);
    for(int i=1;i<=m;i++)bMax.f[i][0]=b[i];
    bMax.init(n);
    for(int i=1;i<=m;i++)bMin.f[i][0]=b[i];
    bMin.init(n);
    //以上是初始化
    while(q--){
        int l1,r1,l2,r2;
        cin>>l1>>r1>>l2>>r2;
        ll ans=LLONG_MIN;//设置为最小值
        int amax=aMax.query(l1,r1);
        int anmx=anegMax.query(l1,r1);
        int apmn=aposMin.query(l1,r1);
        int amin=aMin.query(l1,r1);
        int bmax=bMax.query(l2,r2);
        int bmin=bMin.query(l2,r2);
        ans=max(ans,1LL*amax*(amax>=0?bmin:bmax));
        //a最大值>=0 -> b选最小  a最大值<0 -> b选最大
        ans=max(ans,1LL*amin*(amin>=0?bmin:bmax));
        //a最小值>=0 -> b选最大  a最小值<0 -> b选最小
        if(anmx!=-2e9)ans=max(ans,1LL*anmx*bmax);
        //如果有负数(anmax==-2e9,说明a数组里全是>=0的)
        if(apmn!=2e9)ans=max(ans,1LL*apmn*bmin);
        //如果有正数(apmn==2e9,说明a数组里全是<0的)
        cout<<ans<<"\n";
    }
    return 0;
}