大佬帮我看看为啥会一分没有啊,就是简单地分类讨论
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 1e6 + 5;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int INCF = 0xcfcfcfcf;
int inpt() {
int x = 0, f = 1;
char ch;
for(ch = getchar(); (ch < '0' || ch > '9') && ch != '-'; ch = getchar());
if(ch == '-')
f = -1, ch = getchar();
do {
x = (x << 3) + (x << 1) + ch - '0';
ch = getchar();
}while(ch >= '0' && ch <= '9');
return x * f;
}
int n, m, q;
int A[MAXN], B[MAXN];
struct Seg {
int mn, mx, nt0p, nt0n;
Seg operator + (const Seg &qwq)const {
Seg val;
val.mn = min(mn, qwq.mn);
val.mx = max(mx, qwq.mx);
val.nt0p = min(nt0p, qwq.nt0p);
val.nt0n = max(nt0n, qwq.nt0n);
return val;
}
};
struct SegmentTree {
int l[MAXN << 2], r[MAXN << 2];
int mn[MAXN << 2], mx[MAXN << 2], nt0p[MAXN << 2], nt0n[MAXN << 2];//nearest to 0 positive/negtive
void Update(int x) {
mx[x] = max(mx[x << 1], mx[x << 1 | 1]);
mn[x] = min(mx[x << 1], mn[x << 1 | 1]);
nt0p[x] = min(nt0p[x << 1], nt0p[x << 1 | 1]);
nt0n[x] = max(nt0n[x << 1], nt0n[x << 1 | 1]);
}
void Build(int x, int L, int R, int w[]) {
l[x] = L, r[x] = R;
if(L == R) {
mx[x] = mn[x] = w[L];
nt0p[x] = INF;
nt0n[x] = INCF;
if(w[L] > 0)
nt0p[x] = w[L];
if(w[L] < 0)
nt0n[x] = w[L];
return ;
}
int mid = L + R >> 1;
Build(x << 1, L, mid, w);
Build(x << 1 | 1, mid + 1, R, w);
Update(x);
}
Seg Ask(int x, int L, int R) {
if(L <= l[x] && r[x] <= R)
return {mn[x], mx[x], nt0p[x], nt0n[x]};
int mid = l[x] + r[x] >> 1;
Seg val = {INF, INCF, INF, INCF};
if(L <= mid)
val = val + Ask(x << 1, L, R);
if(R > mid)
val = val + Ask(x << 1 | 1, L, R);
return val;
}
}segA, segB;
void Solve(Seg valA, Seg valB, int l2, int r2) {
if(1ll * valA.nt0p * valB.mn > 1ll * valA.nt0n * valB.mx)
printf("%lld\n", 1ll * valA.nt0p * valB.mn);
else
printf("%lld\n", 1ll * valA.nt0n * valB.mx);
// ll resA = 0, resB = 0;
// bool flag = true;
// if(valA.nt0n == INCF)
// resA = valA.nt0p, flag = false;
// if(valA.nt0p == INF)
// resA = valA.nt0n, flag = false;
// if(flag) {
// if(valA.nt0p * valB.mn > valA.nt0n * valB.mx)
// resA = valA.nt0p;
// else
// resA = valA.nt0n;
// }
//
//// flag = true;
//// if(valB.nt0n == INCF)
//// resB = valB.nt0p, flag = false;
//// if(valA.nt0p == INF)
//// resB = valB.nt0n, flag = false;
//// if(flag) {
////// if(valB.nt0p * valA.mx < valB.nt0n * valA.mn)
////// resB = valB.nt0p;
////// else
////// resB = valB.nt0n;
//// if(resA * valB.mx < resA * valB.mn)
//// resB = valB.mx;
//// else
//// resB = valB.mn;
//// }
//
// ll res = 0x3f3f3f3f3f3f3f3f;
// for(int i = l2; i <= r2; ++i)
// if(resA * B[i] < res)
// res = resA * B[i], resB = B[i];
//
// printf("%lld\n", resA * resB);
}
int main()
{
// freopen("game.in", "r", stdin);
// freopen("game.out", "w", stdout);
n = inpt(), m = inpt(), q = inpt();
for(int i = 1; i <= n; ++i)
A[i] = inpt();
for(int i = 1; i <= m; ++i)
B[i] = inpt();
segA.Build(1, 1, n, A);
segB.Build(1, 1, m, B);
while(q--) {
int l1 = inpt(), r1 = inpt();
int l2 = inpt(), r2 = inpt();
Seg valA = segA.Ask(1, l1, r1);
Seg valB = segB.Ask(1, l2, r2);
if(valA.mn < 0 && valA.mx > 0 && valB.mn < 0 && valB.mx > 0) {// A+-, B+-
Solve(valA, valB, l2, r2);//这一个是假的
}else if(valA.mn <= 0 && valA.mx >= 0 && valB.mn >= 0) {// A+-, B+
printf("%lld\n", 1ll * valA.mx * valB.mn);
}else if(valA.mn <= 0 && valA.mx >= 0 && valB.mx <= 0) {//A+-, B-
printf("%lld\n", 1ll * valA.mn * valB.mx);
}else if(valA.mn >= 0 && valB.mn <= 0 && valB.mx >= 0) {//A+, B+-
printf("%lld\n", 1ll * valA.mn * valB.mn);
}else if(valA.mn >= 0 && valB.mn >= 0) {//A+, B+
printf("%lld\n", 1ll * valA.mx * valB.mn);
}else if(valA.mn >= 0 && valB.mx <= 0) {//A+, B-
printf("%lld\n", 1ll * valA.mn * valB.mn);
}else if(valA.mx <= 0 && valB.mn <= 0 && valB.mx >= 0) {//A-, B+-
printf("%lld\n", 1ll * valA.mx * valB.mx);
}else if(valA.mx <= 0 && valB.mn >= 0) {//A-, B+
printf("%lld\n", 1ll * valA.mx * valB.mx);
}else {//A-, B-
printf("%lld\n", 1ll * valA.mn * valB.mx);
}
}
fclose(stdin);
fclose(stdout);
return 0;
}
/*
6 4 5
3 -1 -2 1 2 0
1 2 -1 -3
1 6 1 4
1 5 1 4
1 4 1 2
2 6 3 4
2 5 2 3
*/