题解说明

问题描述：
给定两个数组 $a$ 和 $b$，每次询问给出区间 $[l_1,r_1]$ 和 $[l_2,r_2]$，要求在 $a[l_1..r_1]$ 与 $b[l_2..r_2]$ 中各选一个数，使得乘积最大。

核心思路：
$1.$ 使用稀疏表 (Sparse Table) 预处理，支持 $O(1)$ 时间查询区间最大值和最小值。

$2.$ 对数组 $a$，拆分为正数数组、负数数组，并单独记录零的位置：

• 正数数组：非正数位置记为 $0$
• 负数数组：非负数位置记为 $0$
• 零：用前缀和记录，判断区间内是否存在零

$3.$ 对数组 $b$，直接构建最大值和最小值稀疏表。

$4.$ 查询时分类讨论：

• 如果 $a$ 区间包含零，则答案至少为 $0$
• 如果 $a$ 区间有正数：
  • 若 $b$ 区间最小值 $<0$，则取 $a$ 区间最小正数 $\times$ $b$ 区间最小值
  • 若 $b$ 区间最小值 $\geq 0$，则取 $a$ 区间最大正数 $\times$ $b$ 区间最小值
• 如果 $a$ 区间有负数：
  • 若 $b$ 区间最大值 $>0$，则取 $a$ 区间最大负数 $\times$ $b$ 区间最大值
  • 若 $b$ 区间最大值 $\leq 0$，则取 $a$ 区间最小负数 $\times$ $b$ 区间最大值

$5.$ 将所有候选结果与初始值比较，取最大值作为答案。

算法流程：
$1.$ 输入数组 $a$，构建正数数组、负数数组和零的前缀和
$2.$ 输入数组 $b$
$3.$ 构建 $6$ 个稀疏表：

• $maxPositive,\ minPositive$
• $maxNegative,\ minNegative$
• $maxB,\ minB$
  $4.$ 对每个查询：
• 查询 $b$ 区间最大值和最小值
• 判断 $a$ 区间是否含零
• 根据正负数情况计算候选答案
• 输出最大值

复杂度分析：

• 预处理：$O((n+m)\log(n+m))$
• 每次查询：$O(1)$
• 总复杂度：$O((n+m)\log(n+m) + q)$

实现细节与注意点：

• 零必须单独处理，否则可能漏掉答案为 $0$ 的情况
• 稀疏表中非目标符号的数用 $\pm INF$ 替代，避免误取
• 稀疏表下标从 $1$ 开始，注意边界
• 查询结果范围在 $long\ long$ 内即可，不会溢出

总结：
该算法通过稀疏表快速区间查询 $+$ 分类讨论，在 $O(1)$ 时间内回答每个查询。整体复杂度优秀，适合大规模数据下的区间乘积最大值问题。

#include <bits/stdc++.h>
using namespace std;

// 类型定义
typedef long long LL;
typedef unsigned long long ULL;
typedef __int128 BigInt;  // 用于处理大整数

// 重载BigInt的输出运算符
inline ostream &operator<<(ostream &cout, BigInt x) {
    static const LL LIMIT = 1e18;
    // 处理大整数输出，拆分为两部分避免溢出
    return x < LIMIT ? cout << (LL)x : cout << (LL)(x / LIMIT) << setw(18) << setfill('0') << (LL)(x % LIMIT);
}

// 常用数据结构定义
typedef pair<int, int> PairInt;
typedef tuple<int, int, int> Tuple3Int;
#define firstElement fi
#define secondElement se

// 通用工具函数
#define allElements(vec) vec.begin(), vec.end()
#define typeReference(type) const type&

template<typename Type>
inline void clearContainer(Type &x) {
    // 清空容器并释放内存
    Type().swap(x);
}

const int MAX_SIZE = 100010;  // 最大数据规模

// 全局变量
int n, m, q;                  // n: 数组a的长度, m: 数组b的长度, q: 查询次数
int positiveNums[MAX_SIZE];   // 存储正数(其他位置为0)
int negativeNums[MAX_SIZE];   // 存储负数(其他位置为0)
int zeroPrefixSum[MAX_SIZE];  // 零的前缀和(用于判断区间是否含零)
int bArray[MAX_SIZE];         // 数组b

// 最大值稀疏表(ST表)实现
struct MaxSparseTable {
    int st[20][MAX_SIZE];  // st[i][j]表示从j开始,长度为2^i的区间的最大值
    
    // 初始化稀疏表
    // a: 原始数组, n: 数组长度, f: 是否直接复制(0:处理0值为INT_MIN, 1:直接复制)
    inline void init(int *a, int n, int f = 0) {
        if (f) {
            // 直接复制数组(用于b数组)
            memcpy(st[0] + 1, a + 1, n * sizeof(int));
        } else {
            // 处理0值为INT_MIN(用于正数数组)
            for (int i = 1; i <= n; ++i) {
                st[0][i] = a[i] != 0 ? a[i] : INT_MIN;
            }
        }
        
        int logMax = __lg(n);  // 计算最大对数
        
        // 构建稀疏表
        for (int i = 1; i <= logMax; ++i) {
            for (int j = 1; j + (1 << i) - 1 <= n; ++j) {
                st[i][j] = max(st[i-1][j], st[i-1][j + (1 << (i-1))]);
            }
        }
    }
    
    // 查询区间[l, r]的最大值
    inline int query(int l, int r) {
        int k = __lg(r - l + 1);  // 计算区间长度的对数
        return max(st[k][l], st[k][r - (1 << k) + 1]);
    }
} maxPositive, maxNegative, maxB;

// 最小值稀疏表(ST表)实现
struct MinSparseTable {
    int st[20][MAX_SIZE];  // st[i][j]表示从j开始,长度为2^i的区间的最小值
    
    // 初始化稀疏表
    // a: 原始数组, n: 数组长度, f: 是否直接复制(0:处理0值为INT_MAX, 1:直接复制)
    inline void init(int *a, int n, int f = 0) {
        if (f) {
            // 直接复制数组(用于b数组)
            memcpy(st[0] + 1, a + 1, n * sizeof(int));
        } else {
            // 处理0值为INT_MAX(用于负数数组)
            for (int i = 1; i <= n; ++i) {
                st[0][i] = a[i] != 0 ? a[i] : INT_MAX;
            }
        }
        
        int logMax = __lg(n);  // 计算最大对数
        
        // 构建稀疏表
        for (int i = 1; i <= logMax; ++i) {
            for (int j = 1; j + (1 << i) - 1 <= n; ++j) {
                st[i][j] = min(st[i-1][j], st[i-1][j + (1 << (i-1))]);
            }
        }
    }
    
    // 查询区间[l, r]的最小值
    inline int query(int l, int r) {
        int k = __lg(r - l + 1);  // 计算区间长度的对数
        return min(st[k][l], st[k][r - (1 << k) + 1]);
    }
} minPositive, minNegative, minB;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    // 读取输入规模
    cin >> n >> m >> q;
    
    // 初始化数组a相关数据结构
    for (int i = 1, x; i <= n; ++i) {
        cin >> x;
        
        if (x > 0) {
            positiveNums[i] = x;      // 记录正数
            negativeNums[i] = 0;      // 正数位置负数数组记为0
        } else if (x < 0) {
            positiveNums[i] = 0;      // 负数位置正数数组记为0
            negativeNums[i] = x;      // 记录负数
        } else {
            positiveNums[i] = 0;      // 零的位置正数数组记为0
            negativeNums[i] = 0;      // 零的位置负数数组记为0
            zeroPrefixSum[i] = 1;     // 标记当前位置是零
        }
        
        // 计算零的前缀和
        zeroPrefixSum[i] += zeroPrefixSum[i-1];
    }
    
    // 读取数组b
    for (int i = 1; i <= m; ++i) {
        cin >> bArray[i];
    }
    
    // 初始化稀疏表
    maxPositive.init(positiveNums, n);    // 正数数组的最大值ST表
    maxNegative.init(negativeNums, n);    // 负数数组的最大值ST表
    maxB.init(bArray, m, 1);              // b数组的最大值ST表
    
    minPositive.init(positiveNums, n);    // 正数数组的最小值ST表
    minNegative.init(negativeNums, n);    // 负数数组的最小值ST表
    minB.init(bArray, m, 1);              // b数组的最小值ST表
    
    // 处理查询
    while (q--) {
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        
        // 获取b数组查询区间的最大最小值
        int bMax = maxB.query(l2, r2);
        int bMin = minB.query(l2, r2);
        
        // 计算结果: 如果a的查询区间包含零,初始化为0;否则初始化为负无穷
        LL result = (zeroPrefixSum[r1] ^ zeroPrefixSum[l1-1]) ? 0 : LLONG_MIN;
        
        // 处理正数情况: 如果a的查询区间有正数
        if (maxPositive.query(l1, r1) > 0) {
            // 根据b的最小值符号选择合适的a值计算乘积
            int aVal = (bMin < 0) ? minPositive.query(l1, r1) : maxPositive.query(l1, r1);
            result = max(result, 1LL * aVal * bMin);
        }
        
        // 处理负数情况: 如果a的查询区间有负数
        if (minNegative.query(l1, r1) < 0) {
            // 根据b的最大值符号选择合适的a值计算乘积
            int aVal = (bMax > 0) ? maxNegative.query(l1, r1) : minNegative.query(l1, r1);
            result = max(result, 1LL * aVal * bMax);
        }
        
        cout << result << '\n';
    }
    
    return 0;
}