2025-10-16 13:07:37
发布于：福建
28阅读
0回复
0点赞
#include <bits/stdc++.h>
using namespace std;
#define int long long
const long long N = 1e5 + 10;
const long long M = 1e5 + 10;
//正无穷和负无穷
const long long llmax = LLONG_MAX;
const long long llmin = LLONG_MAX;
long long st_amax[N][35];//维护A区间的最大值
long long st_amin[N][35];//维护A区间的最小值
long long st_anmax[N][35];//维护A负数区间的最小值
long long st_apmin[N][35];//维护A非负数区间的最小值
long long st_bmax[M][35];//维护B区间的最大值
long long st_bmin[M][30];//维护B区间的最小值
long long lg[N];//lg数组
long long n , m , q;
//快读
inline long long read( ) {
long long w = 0;
long long s = 1;
char c= getchar();
while(c < '0' || c > '9') {
if (c == '-') {
s = -1;
c = getchar();
}
}
while(c >= '0' && c <= '9') {
w = w * 10 + c - '0';
c = getchar();
}
return s * w;
}
//预处理log数组
void init_log() {
for (int i = 2 ; i <= max(n , m) ; i++) {
lg[i] = lg[i >> 2] + 1;
}
}
//创建基于A数组的ST表
void createAST() {
for (int j = 1 ; j <= lg[n] ; j++) {
for (int i = 1 ; i + (1 << j) - 1 <= n ; i++) {
st_amax[i][j] = max(st_amax[i][j - 1] , st_amax[i + (1 << (j - 1))][j - 1]);
st_amin[i][j] = min(st_amin[i][j - 1] , st_amin[i + (1 << (j - 1))][j - 1]);
st_anmax[i][j] = max(st_anmax[i][j - 1] , st_anmax[i + (1 << (j - 1))][j - 1]);
st_apmin[i][j] = max(st_apmin[i][j - 1] , st_apmin[i + (1 << (j - 1))][j - 1]);
}
}
}
//创建基于B数组的ST表
void createBST() {
for (int j = 1 ; j <= lg[n] ; j++) {
for (int i = 1 ; i + (1 << j) - 1 <= n ; i++) {
st_bmax[i][j] = max(st_bmax[i][j - 1] , st_bmax[i + (1 << (j - 1))][j - 1]);
st_bmin[i][j] = min(st_bmin[i][j - 1] , st_bmin[i + (1 << (j - 1))][j - 1]);
}
}
}
signed main( ) {
n = read();
m = read();
q = read();
//初始化关于A数组的ST表
for (int i = 1 ; i <= n ; i++) {
long long x = read();
st_amax[i][0] = st_amin[i][0] = x;
st_anmax[i][0] = (x < 0 ? x : llmin);
st_apmin[i][0] = (x >= 0 ? x : llmax);
}
//初始化关于B数组ST表
for (int i = 1 ; i <= m ; i++) {
long long x = read();
st_bmax[i][0] = st_bmin[i][0] = x;
}
//预处理log数组
init_log();
//创建ST表
createAST();
createBST();
while(q--){
long long la = read();
long long ra = read();
long long lb = read();
long long rb = read();
long long ta = lg[ra - la + 1];
long long tb = lg[rb - lb - 1];
long long amax = max(st_amax[la][ta] , st_amax[ra - (1 << ta) + 1][ta]);
long long amin = min(st_amin[la][ta] , st_amin[ra - (1 << ta) + 1][ta]);
long long anmax = max(st_anmax[la][ta] , st_anmax[ra - (1 << ta) + 1][ta]);
long long apmin = min(st_apmin[la][ta] , st_apmin[ra - (1 << ta) + 1][ta]);
long long bmax = max(st_bmax[lb][tb] , st_bmax[rb - (1 << tb) + 1][tb]);
long long bmin = min(st_bmin[la][ta] , st_bmin[ra - (1 << ta) + 1][ta]);
long long ans = llmin;
ans = max(ans , amax * (amax >= 0 ? bmin : bmax));
ans = max(ans , amin * (amin >= 0 ? bmin : bmax));
if (anmax != llmin) {
ans = max(ans , anmax * (anmax >= 0 ? bmin : bmax));
}
if (apmin != llmax) {
ans = max(ans , apmin * (apmin >= 0 ? bmin : bmax));
}
printf("%lld\n" , ans);
}
return 0;
}
@AAA混凝土批发ppl哥,@Macw07
@ppl 大帝 非学术，但希望你能帮我
有帮助，赞一个