```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
int x = 0, f = 1;
char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-')
f = -1;
ch = getchar();
}
while (isdigit(ch)) {
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
const int INF = 1e9 + 1;
int n, m, q, a[100001], b[100001], zhenga[100001], fua[100001], zeroa[100001], zhengb[100001], fub[100001],
zerob[100001];
namespace SegTreea {
struct Tree {
int l, r;
int MinAbsFu, MinAbsZheng, MaxAbsZheng, MaxAbsFu;
bool zero;
} st[400001];
inline void push_up(int p) {
if (st[p << 1].zero || st[p << 1 | 1].zero) {
st[p].zero = true;
} else {
st[p].zero = false;
}
if (st[p << 1].MinAbsFu == INF) {
if (st[p << 1 | 1].MinAbsFu == INF) {
st[p].MinAbsFu = INF;
} else {
st[p].MinAbsFu = st[p << 1 | 1].MinAbsFu;
}
} else {
if (st[p << 1 | 1].MinAbsFu == INF) {
st[p].MinAbsFu = st[p << 1].MinAbsFu;
} else {
st[p].MinAbsFu = -min(abs(st[p << 1].MinAbsFu), abs(st[p << 1 | 1].MinAbsFu));
}
}
if (st[p << 1].MinAbsZheng == INF) {
if (st[p << 1 | 1].MinAbsZheng == INF) {
st[p].MinAbsZheng = INF;
} else {
st[p].MinAbsZheng = st[p << 1 | 1].MinAbsZheng;
}
} else {
if (st[p << 1 | 1].MinAbsZheng == INF) {
st[p].MinAbsZheng = st[p << 1].MinAbsZheng;
} else {
st[p].MinAbsZheng = min(st[p << 1].MinAbsZheng, st[p << 1 | 1].MinAbsZheng);
}
}
if (st[p << 1].MaxAbsZheng == INF) {
if (st[p << 1 | 1].MaxAbsZheng == INF) {
st[p].MaxAbsZheng = INF;
} else {
st[p].MaxAbsZheng = st[p << 1 | 1].MaxAbsZheng;
}
} else {
if (st[p << 1 | 1].MaxAbsZheng == INF) {
st[p].MaxAbsZheng = st[p << 1].MaxAbsZheng;
} else {
st[p].MaxAbsZheng = max(st[p << 1].MaxAbsZheng, st[p << 1 | 1].MaxAbsZheng);
}
}
if (st[p << 1].MaxAbsFu == INF) {
if (st[p << 1 | 1].MaxAbsFu == INF) {
st[p].MaxAbsFu = INF;
} else {
st[p].MaxAbsFu = st[p << 1 | 1].MaxAbsFu;
}
} else {
if (st[p << 1 | 1].MinAbsFu == INF) {
st[p].MaxAbsFu = st[p << 1].MaxAbsFu;
} else {
st[p].MaxAbsFu = -max(abs(st[p << 1].MaxAbsFu), abs(st[p << 1 | 1].MaxAbsFu));
}
}
return;
}
inline void build(int p, int l, int r) {
st[p].l = l, st[p].r = r;
if (l == r) {
int x = a[l];
if (x > 0) {
st[p].MaxAbsZheng = st[p].MinAbsZheng = x;
st[p].MaxAbsFu = st[p].MinAbsFu = INF;
st[p].zero = false;
} else if (x < 0) {
st[p].MaxAbsZheng = st[p].MinAbsZheng = INF;
st[p].MaxAbsFu = st[p].MinAbsFu = x;
st[p].zero = false;
} else {
st[p].MaxAbsZheng = st[p].MinAbsZheng = INF;
st[p].MaxAbsFu = st[p].MinAbsFu = INF;
st[p].zero = true;
}
return;
}
int mid = (l + r) >> 1;
build(p << 1, l, mid);
build(p << 1 | 1, mid + 1, r);
push_up(p);
return;
}
inline int qMinAbsFu(int l, int r, int p) {
if (st[p].l >= l && st[p].r <= r)
return st[p].MinAbsFu;
int mid = (st[p].l + st[p].r) >> 1;
int temp = INF;
if (l <= mid)
temp = -min(abs(temp), abs(qMinAbsFu(l, r, p << 1)));
if (r > mid)
temp = -min(abs(temp), abs(qMinAbsFu(l, r, p << 1 | 1)));
return temp;
}
inline int qMinAbsZheng(int l, int r, int p) {
if (st[p].l >= l && st[p].r <= r)
return st[p].MinAbsZheng;
int mid = (st[p].l + st[p].r) >> 1;
int temp = INF;
if (l <= mid)
temp = min(temp, qMinAbsZheng(l, r, p << 1));
if (r > mid)
temp = min(temp, qMinAbsZheng(l, r, p << 1 | 1));
return temp;
}
inline int qMaxAbsZheng(int l, int r, int p) {
if (st[p].l >= l && st[p].r <= r) {
if (st[p].MaxAbsZheng != INF)
return st[p].MaxAbsZheng;
else
return 0;
}
int mid = (st[p].l + st[p].r) >> 1;
int temp = 0;
if (l <= mid) {
int wtf = qMaxAbsZheng(l, r, p << 1);
//cout << endl << endl << wtf << endl << endl;
if (wtf != INF)
temp = max(temp, wtf);
}
if (r > mid) {
int wtf = qMaxAbsZheng(l, r, p << 1 | 1);
//cout << endl << endl << wtf << endl << endl;
if (wtf != INF)
temp = max(temp, wtf);
}
return temp;
}
inline int qMaxAbsFu(int l, int r, int p) {
if (st[p].l >= l && st[p].r <= r) {
if (st[p].MaxAbsFu == INF || st[p].MaxAbsFu == -INF) {
return 0;
} else
return st[p].MaxAbsFu;
}
int mid = (st[p].l + st[p].r) >> 1;
int temp = 0;
if (l <= mid)
temp = -max(abs(temp), abs(qMaxAbsFu(l, r, p << 1)));
if (r > mid)
temp = -max(abs(temp), abs(qMaxAbsFu(l, r, p << 1 | 1)));
return temp;
}
}
namespace SegTreeb {
struct Tree {
int l, r;
int MinAbsFu, MinAbsZheng, MaxAbsZheng, MaxAbsFu;
bool zero;
} st[400001];
inline void push_up(int p) {
if (st[p << 1].zero || st[p << 1 | 1].zero) {
st[p].zero = true;
} else {
st[p].zero = false;
}
if (st[p << 1].MinAbsFu == INF) {
if (st[p << 1 | 1].MinAbsFu == INF) {
st[p].MinAbsFu = INF;
} else {
st[p].MinAbsFu = st[p << 1 | 1].MinAbsFu;
}
} else {
if (st[p << 1 | 1].MinAbsFu == INF) {
st[p].MinAbsFu = st[p << 1].MinAbsFu;
} else {
st[p].MinAbsFu = -min(abs(st[p << 1].MinAbsFu), abs(st[p << 1 | 1].MinAbsFu));
}
}
if (st[p << 1].MinAbsZheng == INF) {
if (st[p << 1 | 1].MinAbsZheng == INF) {
st[p].MinAbsZheng = INF;
} else {
st[p].MinAbsZheng = st[p << 1 | 1].MinAbsZheng;
}
} else {
if (st[p << 1 | 1].MinAbsZheng == INF) {
st[p].MinAbsZheng = st[p << 1].MinAbsZheng;
} else {
st[p].MinAbsZheng = min(st[p << 1].MinAbsZheng, st[p << 1 | 1].MinAbsZheng);
}
}
if (st[p << 1].MaxAbsZheng == INF) {
if (st[p << 1 | 1].MaxAbsZheng == INF) {
st[p].MaxAbsZheng = INF;
} else {
st[p].MaxAbsZheng = st[p << 1 | 1].MaxAbsZheng;
}
} else {
if (st[p << 1 | 1].MaxAbsZheng == INF) {
st[p].MaxAbsZheng = st[p << 1].MaxAbsZheng;
} else {
st[p].MaxAbsZheng = max(st[p << 1].MaxAbsZheng, st[p << 1 | 1].MaxAbsZheng);
}
}
if (st[p << 1].MaxAbsFu == INF) {
if (st[p << 1 | 1].MaxAbsFu == INF) {
st[p].MaxAbsFu = INF;
} else {
st[p].MaxAbsFu = st[p << 1 | 1].MaxAbsFu;
}
} else {
if (st[p << 1 | 1].MinAbsFu == INF) {
st[p].MaxAbsFu = st[p << 1].MaxAbsFu;
} else {
st[p].MaxAbsFu = -max(abs(st[p << 1].MaxAbsFu), abs(st[p << 1 | 1].MaxAbsFu));
}
}
return;
}
inline void build(int p, int l, int r) {
st[p].l = l, st[p].r = r;
if (l == r) {
int x = b[l];
if (x > 0) {
st[p].MaxAbsZheng = st[p].MinAbsZheng = x;
st[p].MaxAbsFu = st[p].MinAbsFu = INF;
st[p].zero = false;
} else if (x < 0) {
st[p].MaxAbsZheng = st[p].MinAbsZheng = INF;
st[p].MaxAbsFu = st[p].MinAbsFu = x;
st[p].zero = false;
} else {
st[p].MaxAbsZheng = st[p].MinAbsZheng = INF;
st[p].MaxAbsFu = st[p].MinAbsFu = INF;
st[p].zero = true;
}
return;
}
int mid = (l + r) >> 1;
build(p << 1, l, mid);
build(p << 1 | 1, mid + 1, r);
push_up(p);
return;
}
inline int qMinAbsFu(int l, int r, int p) {
if (st[p].l >= l && st[p].r <= r)
return st[p].MinAbsFu;
int mid = (st[p].l + st[p].r) >> 1;
int temp = INF;
if (l <= mid)
temp = -min(abs(temp), abs(qMinAbsFu(l, r, p << 1)));
if (r > mid)
temp = -min(abs(temp), abs(qMinAbsFu(l, r, p << 1 | 1)));
return temp;
}
inline int qMinAbsZheng(int l, int r, int p) {
if (st[p].l >= l && st[p].r <= r)
return st[p].MinAbsZheng;
int mid = (st[p].l + st[p].r) >> 1;
int temp = INF;
if (l <= mid)
temp = min(temp, qMinAbsZheng(l, r, p << 1));
if (r > mid)
temp = min(temp, qMinAbsZheng(l, r, p << 1 | 1));
return temp;
}
inline int qMaxAbsZheng(int l, int r, int p) {
if (st[p].l >= l && st[p].r <= r) {
if (st[p].MaxAbsZheng != INF)
return st[p].MaxAbsZheng;
else
return 0;
}
int mid = (st[p].l + st[p].r) >> 1;
int temp = 0;
if (l <= mid) {
int wtf = qMaxAbsZheng(l, r, p << 1);
//cout << endl << endl << wtf << endl << endl;
if (wtf != INF)
temp = max(temp, wtf);
}
if (r > mid) {
int wtf = qMaxAbsZheng(l, r, p << 1 | 1);
//cout << endl << endl << wtf << endl << endl;
if (wtf != INF)
temp = max(temp, wtf);
}
return temp;
}
inline int qMaxAbsFu(int l, int r, int p) {
if (st[p].l >= l && st[p].r <= r) {
if (st[p].MaxAbsFu == INF || st[p].MaxAbsFu == -INF) {
return 0;
} else
return st[p].MaxAbsFu;
}
int mid = (st[p].l + st[p].r) >> 1;
int temp = 0;
if (l <= mid)
temp = -max(abs(temp), abs(qMaxAbsFu(l, r, p << 1)));
if (r > mid)
temp = -max(abs(temp), abs(qMaxAbsFu(l, r, p << 1 | 1)));
return temp;
}
}
inline int getzha(int l, int r) {
return zhenga[r] - zhenga[l - 1];
}
inline int getzhb(int l, int r) {
return zhengb[r] - zhengb[l - 1];
}
inline int getfua(int l, int r) {
return fua[r] - fua[l - 1];
}
inline int getfub(int l, int r) {
return fub[r] - fub[l - 1];
}
inline int get0a(int l, int r) {
return zeroa[r] - zeroa[l - 1];
}
inline int get0b(int l, int r) {
return zerob[r] - zerob[l - 1];
}
inline void init() {
SegTreea::build(1, 1, n);
SegTreeb::build(1, 1, m);
for (int i = 1; i <= n; i++) {
zhenga[i] = zhenga[i - 1];
fua[i] = fua[i - 1];
zeroa[i] = zeroa[i - 1];
if (a[i] > 0)
zhenga[i]++;
if (a[i] < 0)
fua[i]++;
if (a[i] == 0)
zeroa[i]++;
}
for (int i = 1; i <= m; i++) {
zhengb[i] = zhengb[i - 1];
fub[i] = fub[i - 1];
zerob[i] = zerob[i - 1];
if (b[i] > 0)
zhengb[i]++;
if (b[i] < 0)
fub[i]++;
if (b[i] == 0)
zerob[i]++;
}
return;
}
inline int Solve(int l1, int r1, int l2, int r2) {
int L, Q;
if (!getzhb(l2, r2)) {
if (getfua(l1, r1) > 0)
L = SegTreea::qMaxAbsFu(l1, r1, 1);
else if (get0a(l1, r1) > 0)
L = 0;
else
L = SegTreea::qMinAbsZheng(l1, r1, 1);
} else if (!getfub(l2, r2)) {
if (getzha(l1, r1) > 0)
L = SegTreea::qMaxAbsZheng(l1, r1, 1);
else if (get0a(l1, r1) > 0)
L = 0;
else
L = SegTreea::qMinAbsFu(l1, r1, 1);
} else {
if (get0a(l1, r1) > 0)
L = 0;
else {
int q1 = SegTreeb::qMaxAbsZheng(l2, r2, 1);
int q2 = SegTreeb::qMaxAbsFu(l2, r2, 1);
int L1 = SegTreea::qMinAbsZheng(l1, r1, 1);
int L2 = SegTreea::qMinAbsFu(l1, r1, 1);
//cout << L1 << " " << L2 << endl;
if (L1 * q2 > L2 * q1) {
L = L1;
} else {
L = L2;
}
}
}
if (L > 0) {
if (getfub(l2, r2) > 0) {
Q = SegTreeb::qMaxAbsFu(l2, r2, 1);
} else if (get0b(l2, r2) > 0) {
Q = 0;
} else {
Q = SegTreeb::qMinAbsZheng(l2, r2, 1);
}
} else if (L == 0) {
return 0;
} else {
if (getzhb(l2, r2) > 0) {
Q = SegTreeb::qMaxAbsZheng(l2, r2, 1);
} else if (get0b(l2, r2) > 0) {
Q = 0;
} else {
Q = SegTreeb::qMinAbsFu(l2, r2, 1);
}
}
return L * Q;
}
signed main() {
n = read();
m = read();
q = read();
for (int i = 1; i <= n; i++)
a[i] = read();
for (int i = 1; i <= m; i++)
b[i] = read();
init();
//cout << SegTreeb::qMaxAbsFu(2, 3, 1) << endl;
//return 0;
while (q--) {
int l1, r1, l2, r2;
l1 = read();
r1 = read();
l2 = read();
r2 = read();
printf("%lld\n", Solve(l1, r1, l2, r2));
}
return 0;
}
```
by zhang_kevin @ 2024-07-21 12:35:33