线段树最后一个点wa了,头发快掉光了。
#include <bits/stdc++.h>
#define ll long long
#define BZHZS puts("BZH is a handsome boy.");
using namespace std;
const int N = 100010;
struct node
{
ll zmaxx, zminn, fmaxx, fminn;
};
int n, m, q, xa, ya, xb, yb;
ll a[N], b[N], a0[N], b0[N], ans, roc;
node at[4 * N], bt[4 * N], sa, sb;
inline ll read()
{
ll f = 1, s = 0;
char c = getchar();
while (c < '0' || c > '9')
{
if (c == '-')
f = -1;
c = getchar();
}
while (c >= '0' && c <= '9')
{
s = (s << 1) + (s << 3) + c - '0';
c = getchar();
}
return s * f;
}
void builda(int x, int l, int r)
{
if (l == r)
{
if (a[l] > 0)
{
at[x] = node{a[l], a[l], INT_MIN, 0};
// printf("%lld %lld %lld %lld\n", at[x].zmaxx, at[x].zminn, at[x].fmaxx, at[x].fminn);
}
else if (a[l] < 0)
{
at[x] = node{0, INT_MAX, a[l], a[l]};
// printf("%lld %lld %lld %lld\n", at[x].zmaxx, at[x].zminn, at[x].fmaxx, at[x].fminn);
}
else
{
at[x] = node{0, INT_MAX, INT_MIN, 0};
}
return;
}
int mid = (l + r) / 2;
builda(x * 2, l, mid);
builda(x * 2 + 1, mid + 1, r);
at[x].fmaxx = max(at[x * 2].fmaxx, at[x * 2 + 1].fmaxx);
at[x].fminn = min(at[x * 2].fminn, at[x * 2 + 1].fminn);
at[x].zmaxx = max(at[x * 2].zmaxx, at[x * 2 + 1].zmaxx);
at[x].zminn = min(at[x * 2].zminn, at[x * 2 + 1].zminn);
// printf("%lld %lld %lld %lld\n", at[x].zmaxx, at[x].zminn, at[x].fmaxx, at[x].fminn);
}
void buildb(int x, int l, int r)
{
if (l == r)
{
if (b[l] > 0)
{
bt[x] = node{b[l], b[l], INT_MIN, 0};
}
else if (b[l] < 0)
{
bt[x] = node{0, INT_MAX, b[l], b[l]};
}
else
{
bt[x] = node{0, INT_MAX, INT_MIN, 0};
}
return;
}
int mid = (l + r) / 2;
buildb(x * 2, l, mid);
buildb(x * 2 + 1, mid + 1, r);
bt[x].fmaxx = max(bt[x * 2].fmaxx, bt[x * 2 + 1].fmaxx);
bt[x].fminn = min(bt[x * 2].fminn, bt[x * 2 + 1].fminn);
bt[x].zmaxx = max(bt[x * 2].zmaxx, bt[x * 2 + 1].zmaxx);
bt[x].zminn = min(bt[x * 2].zminn, bt[x * 2 + 1].zminn);
}
node finda(int x, int L, int R, int l, int r)
{
if (l <= L && R <= r)
{
return at[x];
}
int mid = (L + R) / 2;
node res = node{0, INT_MAX, INT_MIN, 0}, tl = node{0, INT_MAX, INT_MIN, 0}, tr = node{0, INT_MAX, INT_MIN, 0};
if (l <= mid)
tl = finda(x * 2, L, mid, l, r);
if (mid < r)
tr = finda(x * 2 + 1, mid + 1, R, l, r);
res.fmaxx = max(tl.fmaxx, tr.fmaxx);
res.fminn = min(tl.fminn, tr.fminn);
res.zmaxx = max(tl.zmaxx, tr.zmaxx);
res.zminn = min(tl.zminn, tr.zminn);
return res;
}
node findb(int x, int L, int R, int l, int r)
{
if (l <= L && R <= r)
{
return bt[x];
}
int mid = (L + R) / 2;
node res = node{0, INT_MAX, INT_MIN, 0}, tl = node{0, INT_MAX, INT_MIN, 0}, tr = node{0, INT_MAX, INT_MIN, 0};
if (l <= mid)
tl = findb(x * 2, L, mid, l, r);
if (mid < r)
tr = findb(x * 2 + 1, mid + 1, R, l, r);
res.fmaxx = max(tl.fmaxx, tr.fmaxx);
res.fminn = min(tl.fminn, tr.fminn);
res.zmaxx = max(tl.zmaxx, tr.zmaxx);
res.zminn = min(tl.zminn, tr.zminn);
return res;
}
int main()
{
// ios::sync_with_stdio(0);
// cin.tie(0), cout.tie(0);
// freopen("BZHZS.in", "r", stdin);
// freopen("BZHZS.out", "w", stdout);
n = read(), m = read(), q = read();
for (int i = 1; i <= n; i++)
a[i] = read(), a0[i] = a0[i - 1] + (a[i] == 0);
for (int i = 1; i <= m; i++)
b[i] = read(), b0[i] = b0[i - 1] + (b[i] == 0);
builda(1, 1, n);
buildb(1, 1, m);
for (int i = 1; i <= q; i++)
{
roc = LONG_LONG_MIN;
xa = read(), ya = read(), xb = read(), yb = read();
sa = finda(1, 1, n, xa, ya);
sb = findb(1, 1, m, xb, yb);
// printf("%lld %lld %lld %lld :: %lld %lld %lld %lld\n", sa.zmaxx, sa.zminn, sa.fmaxx, sa.fminn, sb.zmaxx, sb.zminn, sb.fmaxx, sb.fminn);
if (sa.zmaxx != 0)
{
if (sb.fminn != 0)
{
roc = max(roc, sa.zmaxx * sb.fminn);
}
else
{
roc = max(roc, sa.zmaxx * sb.zminn);
}
}
if (sa.zminn != INT_MAX)
{
if (sb.fminn != 0)
{
roc = max(roc, sa.zminn * sb.fminn);
}
else
{
roc = max(roc, sa.zminn * sb.zminn);
}
}
if (sa.fmaxx != INT_MIN)
{
if (sb.zmaxx != 0)
{
roc = max(roc, sa.fmaxx * sb.zmaxx);
}
else
{
roc = max(roc, sa.fmaxx * sb.fmaxx);
}
}
if (sa.fminn != 0)
{
if (sb.zmaxx != 0)
{
roc = max(roc, sa.fminn * sb.zmaxx);
}
else
{
roc = max(roc, sa.fminn * sb.fmaxx);
}
}
if (roc < 0 && a0[ya] - a0[xa] > 0)
{
puts("0");
}
else if (roc > 0 && b0[yb] - b0[xb] > 0)
{
puts("0");
}
else
{
printf("%lld\n", roc);
}
}
return 0;
}