最新代码
```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5;
int n, m, q, a[N], b[N], dp[N][21], dp2[N][21], dp3[N][21], dp4[N][21], dp5[N][21], dp6[N][21], l, r, x, y, ans;
//dp a区间最大
//dp2 a区间最小
//dp3 b区间最大
//dp4 b区间最小
//dp5 a区间最小非负数
//dp6 a区间最大负数
int query (int l, int r){
int tmp = log2 (r - l + 1);
return max (dp[l][tmp], dp[r - (1 << tmp) + 1][tmp]);
}
int query2 (int l, int r){
int tmp = log2 (r - l + 1);
return min (dp2[l][tmp], dp2[r - (1 << tmp) + 1][tmp]);
}
int query3 (int l, int r){
int tmp = log2 (r - l + 1);
return max (dp3[l][tmp], dp3[r - (1 << tmp) + 1][tmp]);
}
int query4 (int l, int r){
int tmp = log2 (r - l + 1);
return min (dp4[l][tmp], dp4[r - (1 << tmp) + 1][tmp]);
}
int query5 (int l, int r){
int tmp = log2 (r - l + 1);
return min (dp5[l][tmp], dp5[r - (1 << tmp) + 1][tmp]);
}
int query6 (int l, int r){
int tmp = log2 (r - l + 1);
return max (dp6[l][tmp], dp6[r - (1 << tmp) + 1][tmp]);
}
signed main (){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m >> q;
for (int i = 1; i <= n; ++i){
cin >> a[i];
dp[i][0] = a[i];
dp2[i][0] = a[i];
if (a[i] >= 0){
dp5[i][0] = a[i];
dp6[i][0] = -1e18 - 1;
}
else{
dp6[i][0] = a[i];
dp5[i][0] = 1e18;
}
}
for (int i = 1; i <= m; ++i){
cin >> b[i];
dp3[i][0] = b[i];
dp4[i][0] = b[i];
}
for (int j = 1; (1 << j) <= n; ++j){
for (int i = 0; i + (1 << j) - 1 <= n; ++i){
dp[i][j] = max (dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
dp2[i][j] = min (dp2[i][j - 1], dp2[i + (1 << (j - 1))][j - 1]);
dp5[i][j] = min (dp5[i][j - 1], dp5[i + (1 << (j - 1))][j - 1]);
dp6[i][j] = max (dp6[i][j - 1], dp6[i + (1 << (j - 1))][j - 1]);
}
}
for (int j = 1; (1 << j) <= m; ++j){
for (int i = 0; i + (1 << j) - 1 <= m; ++i){
dp3[i][j] = max (dp3[i][j - 1], dp3[i + (1 << (j - 1))][j - 1]);
dp4[i][j] = min (dp4[i][j - 1], dp4[i + (1 << (j - 1))][j - 1]);
}
}
while (q --){
cin >> l >> r >> x >> y;
ans = LONG_LONG_MIN;
int pos = query4 (x, y), posl;
if (pos < 0) posl = query5 (l, r);
if (pos >= 0) posl = query (l, r);
if (abs (pos * posl) < 1e18) ans = pos * posl;
pos = query3 (x, y);
if (pos >= 0) posl = query6 (l, r);
else posl = query2 (l, r);
if (abs (pos * posl) < 1e18) ans = max (ans, pos * posl);
cout << ans << '\n';
}
return 0;
}
by huyangmu @ 2024-07-26 10:10:23
@[GenesisCrystal](/user/681755) 你的dp4 和 dp5 没有设初值是负无穷
by GenesisCrystal @ 2024-07-26 10:11:54
@[GenesisCrystal](/user/681755) 应该不用吧。
by huyangmu @ 2024-07-26 10:16:39
@[GenesisCrystal](/user/681755) 已经用 $3$ 个小号关注
by huyangmu @ 2024-07-26 10:17:02
@[huyangmu](/user/632311) ST表不是求区间最小需要先初始化吗,
by GenesisCrystal @ 2024-07-26 10:18:38
@[GenesisCrystal](/user/681755) 不用吧,我昨天听apple365说的
by huyangmu @ 2024-07-26 10:22:39
@[apple365](/user/123216)
by huyangmu @ 2024-07-26 10:23:06
@[huyangmu](/user/632311) 啊?
by GenesisCrystal @ 2024-07-26 10:34:27
@[GenesisCrystal](/user/681755) 就是我们的信息老师
by huyangmu @ 2024-07-26 10:39:12
@[huyangmu](/user/632311) 没事 at 杨老师干嘛?
by lihongqian__int128 @ 2024-07-26 11:11:14