原题链接
学习笔记
感觉非常复杂？对于现在的我还是有深度的，首先第一个大坑就是并不需要真的求出c矩阵，这个题意就是让你在区间中选数，但要求乘积最大，所以要分讨。
你假定 \(a_i\ge0\)，那这时如果 \(min(b_i)\ge0\) 取 \(max(a_i)\)，否则取 \(min(a_i\ge0)\)，相反的，假定\(a_i<0\)，那这时如果 \(max(b_i)\ge0\) 取 \(max(a_i)\)，否则取 \(max(a_i<0)\)。
这就是贪心的思想，感觉非常有深度（菜），然后就需要维护6个ST表，非常糟糕啊，然后就没有然后了，你就慢慢维护去吧。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+10;int a[N],b[N],lg[N];
int n,m,q;int mxa[N][20];
int mia[N][20];
int rmxa[N][20];
int rmia[N][20];int mxb[N][20];
int mib[N][20];int main(){ios::sync_with_stdio(false);cin>>n>>m>>q;lg[1]=0;for(int i=2;i<=max(n,m);i++){lg[i]=lg[i>>1]+1;}for(int i=1;i<=n;i++){cin>>a[i];mxa[i][0]=mia[i][0]=a[i];rmia[i][0]=0<=a[i]?a[i]:INT_MAX;//正数中取最小，没正数取intmin标记为无 rmxa[i][0]=a[i]<0?a[i]:INT_MIN;//负数中取最大，没负数取intmax标记为无 }for(int i=1;i<=m;i++){cin>>b[i];mxb[i][0]=mib[i][0]=b[i];}for(int j=1;j<=lg[n];j++){for(int i=1;i<=n-(1<<j)+1;i++){int p=i+(1<<(j-1));mxa[i][j]=max(mxa[i][j-1],mxa[p][j-1]);rmxa[i][j]=max(rmxa[i][j-1],rmxa[p][j-1]);mia[i][j]=min(mia[i][j-1],mia[p][j-1]);rmia[i][j]=min(rmia[i][j-1],rmia[p][j-1]);}}for(int j=1;j<=lg[m];j++){for(int i=1;i<=n-(1<<j)+1;i++){int p=i+(1<<(j-1));mxb[i][j]=max(mxb[i][j-1],mxb[p][j-1]);mib[i][j]=min(mib[i][j-1],mib[p][j-1]);}}while(q--){int la,ra,lb,rb;cin>>la>>ra>>lb>>rb;int x=lg[ra-la+1],y=lg[rb-lb+1];int pa=ra-(1<<x)+1,pb=rb-(1<<y)+1;int mmxa=max(mxa[la][x],mxa[pa][x]);int rmmxa=max(rmxa[la][x],rmxa[pa][x]);int mmia=min(mia[la][x],mia[pa][x]);int rmmia=min(rmia[la][x],rmia[pa][x]);int mmxb=max(mxb[lb][y],mxb[pb][y]);int mmib=min(mib[lb][y],mib[pb][y]);long long ans=LONG_LONG_MIN;ans=max(ans,(ll)mmxa*(mmxa>=0?mmib:mmxb));ans=max(ans,(ll)mmia*(mmia>=0?mmib:mmxb));if(rmmxa!=INT_MIN){ans=max(ans,(ll)rmmxa*(rmmxa>=0?mmib:mmxb));} if(rmmia!=INT_MAX){ans=max(ans,(ll)rmmia*(rmmia>=0?mmib:mmxb));}cout<<ans<<"\n";}return 0;
}
