玄4关
by huyangmu @ 2024-07-26 09:43:33
@[huyangmu](/user/632311) 建议把 `query` 改成可读的函数名
by GenesisCrystal @ 2024-07-26 09:51:02
@[GenesisCrystal](/user/681755) 可读的函数名是什么
by huyangmu @ 2024-07-26 09:52:04
@[huyangmu](/user/632311) 看不懂你的 ```query``` 分别啥意思
by lihongqian__int128 @ 2024-07-26 09:54:39
@[huyangmu](/user/632311) 说错了，应该是注释每一个 `query` 的用处，像这样：
```cpp
/*
...
/*
A正区间最大 = A区间最大 : st1
A正区间最小 : st2
A负区间最大 : st3
A负区间最小 = A区间最小 : st1
B正区间最大 = B区间最大 : st4
B正区间最小 : st5
B负区间最大 : st6
B负区间最小 = B区间最小 : st4
*/
...
```
by GenesisCrystal @ 2024-07-26 09:55:49
@[lihongqian__int128](/user/770891) $dp_{i,j}$ 维护数组 $a $ 的区间最大值 $dp2_{i,j}$ 维护数组 $b$ 的区间最小值，$dp3_{i,j}$ 维护数组 $b$ 的区间最大值，$dp4_{i,j}$ 维护数组 $b$ 的区间最小值，$dp5_{i,j}$ 维护数组 $a$ 区间中非负数的最小值，$dp6_{i,j}$ 维护数组 $a$ 中的区间最大负数
by huyangmu @ 2024-07-26 09:58:46
@[GenesisCrystal](/user/681755)
注释版代码
```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 = -1;
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:01:47
@[huyangmu](/user/632311) 首先，ans定-1有点小吧
by GenesisCrystal @ 2024-07-26 10:05:59
@[GenesisCrystal](/user/681755) 确实，但还是有问题
by huyangmu @ 2024-07-26 10:07:58
@[huyangmu](/user/632311) 你的dp4 和 dp5 没有设初值是负无穷
by GenesisCrystal @ 2024-07-26 10:08:57