思路与算法

区间内B的最小最大值决定固定a的最坏收益min(aBmin,aBmax)。A只需检查最小值、最大值、最小正数、最大负数及是否含0。建立两个静态线段树，合并这些摘要，每次查询两段后枚举至多五个a取最优。

正确性说明

小L固定a后，小Q总能把线性乘积降到B某一端点。对a≥0和a<0分别看收益，都是一条线性函数，最优a在该符号区间的最靠近0或最远离0的端点；全体极值与最近0正负数覆盖这些候选，0单独覆盖。线段树摘要合并保持真实区间的极值与存在性，所以每次查询给准确极大极小值。

复杂度

含树初始化，O(n+m+q log(n+m))时间、O(n+m)空间，查询候选为常数个。

易错点

不是同时任选最大乘积；对方会最小化。0和全正/全负范围分别处理；1e9乘积用64位，空正负候选不可参与。原排版负号按半角整数读入。

参考代码（C++11）

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

const long long INF = 4000000000000000000LL;
struct Info {
    long long mn, mx, pos, neg;
    bool zero;
    Info(long long a = INF, long long b = -INF, long long c = INF, long long d = -INF,
         bool z = false)
        : mn(a), mx(b), pos(c), neg(d), zero(z) {
    }
};
Info mergeInfo(Info a, Info b) {
    return {min(a.mn, b.mn), max(a.mx, b.mx), min(a.pos, b.pos), max(a.neg, b.neg),
            a.zero || b.zero};
}
struct Seg {
    int size;
    vector<Info> t;
    Seg(const vector<long long> &a) {
        size = 1;
        while (size < (int)a.size())
            size *= 2;
        t.resize(size * 2);
        for (int i = 0; i < (int)a.size(); i++)
            t[size + i] = {a[i], a[i], a[i] > 0 ? a[i] : INF, a[i] < 0 ? a[i] : -INF, a[i] == 0};
        for (int i = size - 1; i; i--)
            t[i] = mergeInfo(t[2 * i], t[2 * i + 1]);
    }
    Info query(int l, int r) {
        Info v;
        for (l += size, r += size; l < r; l /= 2, r /= 2) {
            if (l & 1)
                v = mergeInfo(v, t[l++]);
            if (r & 1)
                v = mergeInfo(v, t[--r]);
        }
        return v;
    }
};
int main() {
    int n, m, q;
    cin >> n >> m >> q;
    vector<long long> a(n), b(m);
    for (auto &x : a)
        cin >> x;
    for (auto &x : b)
        cin >> x;
    Seg A(a), B(b);
    while (q--) {
        int l, r, x, y;
        cin >> l >> r >> x >> y;
        Info aa = A.query(l - 1, r), bb = B.query(x - 1, y);
        long long ans = -INF;
        vector<long long> cand = {aa.mn, aa.mx};
        if (aa.pos != INF)
            cand.push_back(aa.pos);
        if (aa.neg != -INF)
            cand.push_back(aa.neg);
        if (aa.zero)
            cand.push_back(0);
        for (long long z : cand)
            ans = max(ans, min(z * bb.mn, z * bb.mx));
        cout << ans << "\n";
    }
}