ST表的板子题

写之前学一下板子就行了

#include <bits/stdc++.h>
using namespace std;
long long n,m,q,a[100010],b[100010];
const int maxn=1e5+10;
const int lg=__lg(maxn);
struct stmx{
    int table[maxn][lg+1];
    void init(int n){
        for(int j=1;j<=lg;j++){
            int x=1<<(j-1);
            for(int i=1;i<=n-x;i++){
                table[i][j]=max(table[i][j-1],table[i+x][j-1]);
            }
        }
    }
    int q(int l,int r){
        int tmp=__lg(r-l+1);
        return max(table[l][tmp],table[r-(1<<tmp)+1][tmp]);
    }
};
struct stmn{
    int table[maxn][lg+1];
    void init(int n){
        for(int j=1;j<=lg;j++){
            int x=1<<(j-1);
            for(int i=1;i<=n-x;i++){
                table[i][j]=min(table[i][j-1],table[i+x][j-1]);
            }
        }
    }
    int q(int l,int r){
        int tmp=__lg(r-l+1);
        return min(table[l][tmp],table[r-(1<<tmp)+1][tmp]);
    }
};
stmx amx,anmx,bmx;
stmn amn,apmn,bmn;
int main(){
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        amx.table[i][0]=a[i];
        amn.table[i][0]=a[i];
        if(a[i]>=0) anmx.table[i][0]=-2e9;
        else anmx.table[i][0]=a[i];
        if(a[i]>=0) apmn.table[i][0]=a[i];
        else apmn.table[i][0]=2e9;
    }
    amx.init(n+1);
    amn.init(n+1);
    anmx.init(n+1);
    apmn.init(n+1);
    for(int i=1;i<=m;i++){
        cin>>b[i];
        bmx.table[i][0]=b[i];
        bmn.table[i][0]=b[i];
    }
    bmx.init(m+1);
    bmn.init(m+1);
    while(q--){
        int l1,r1,l2,r2;
        cin>>l1>>r1>>l2>>r2;
        long long ans=LLONG_MIN;
        int amax=amx.q(l1,r1),amin=amn.q(l1,r1),aposmn=apmn.q(l1,r1),anegmx=anmx.q(l1,r1),bmax=bmx.q(l2,r2),bmin=bmn.q(l2,r2);
        ans=max(ans,(long long)amax*(amax>=0?bmin:bmax));
        ans=max(ans,(long long)amin*(amin>=0?bmin:bmax));
        if(anegmx!=-2e9)ans=max(ans,(long long)anegmx*bmax);
        if(aposmn!=2e9)ans=max(ans,(long long)aposmn*bmin);
        cout<<ans<<endl;
    }
    return 0;
}