记录编号	601064	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	3782.[CSP 2022S]策略游戏	最终得分	100
用户昵称	zjzhe	是否通过	通过
代码语言	C++	运行时间	5.132 s
提交时间	2025-05-29 16:00:29	内存使用	41.58 MiB

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=1e5+15;
int n,m,q,a[N],b[N],lg[N],minA[N][20],maxA[N][20],minAZ[N][20],maxAF[N][20],minB[N][20],maxB[N][20];
#undef int 
int main(){
#define int long long 
    freopen("csp2022_game.in","r",stdin);
    freopen("csp2022_game.out","w",stdout);
    cin>>n>>m>>q;lg[1]=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        maxA[i][0]=minA[i][0]=a[i];
        if(a[i]>=0)minAZ[i][0]=a[i],maxAF[i][0]=-1e9;
        else minAZ[i][0]=1e9,maxAF[i][0]=a[i];
    }
    for(int i=1;i<=m;i++){
        cin>>b[i];
        maxB[i][0]=minB[i][0]=b[i];
    }
    for(int i=2;i<=max(n,m);i++)lg[i]=lg[i>>1]+1;
    int t=lg[n]+1;
    for(int j=1;j<t;j++){
        for(int i=1;i<=n-(1<<j)+1;i++){
            maxA[i][j]=max(maxA[i][j-1],maxA[i+(1<<(j-1))][j-1]);
            minA[i][j]=min(minA[i][j-1],minA[i+(1<<(j-1))][j-1]);
            maxAF[i][j]=max(maxAF[i][j-1],maxAF[i+(1<<(j-1))][j-1]);
            minAZ[i][j]=min(minAZ[i][j-1],minAZ[i+(1<<(j-1))][j-1]);
            maxB[i][j]=max(maxB[i][j-1],maxB[i+(1<<(j-1))][j-1]);
            minB[i][j]=min(minB[i][j-1],minB[i+(1<<(j-1))][j-1]);
        }
    }
    t=lg[m]+1;
    for(int j=1;j<t;j++){
        for(int i=1;i<=m-(1<<j)+1;i++){
            maxB[i][j]=max(maxB[i][j-1],maxB[i+(1<<(j-1))][j-1]);
            minB[i][j]=min(minB[i][j-1],minB[i+(1<<(j-1))][j-1]);
        }
    }
    for(;q;q--){
        int l1,r1,l2,r2;
        cin>>l1>>r1>>l2>>r2;
        int k=lg[r1-l1+1],mxA,mxB,miA,miB,mxAF,miAZ;
        mxA=max(maxA[l1][k],maxA[r1-(1<<k)+1][k]);
        miA=min(minA[l1][k],minA[r1-(1<<k)+1][k]);
        mxAF=max(maxAF[l1][k],maxAF[r1-(1<<k)+1][k]);
        miAZ=min(minAZ[l1][k],minAZ[r1-(1<<k)+1][k]);
        k=lg[r2-l2+1];
        mxB=max(maxB[l2][k],maxB[r2-(1<<k)+1][k]);
        miB=min(minB[l2][k],minB[r2-(1<<k)+1][k]);
        //cout<<mxA<<' '<<miA<<' '<<mxAF<<' '<<miAZ<<'\n';
        //cout<<mxB<<' '<<miB<<'\n';
        int ans=-1e18;
        if(mxA>=0)ans=max(ans,mxA*miB);
        else ans=max(ans,mxA*mxB);
        if(miA>=0)ans=max(ans,miA*miB);
        else ans=max(ans,miA*mxB);
        if(miAZ!=1e9)ans=max(ans,miAZ*miB);
        if(mxAF!=-1e9)ans=max(ans,mxAF*mxB);
        cout<<ans<<'\n';
    }
    return 0;
}