算法分析
首先使用贪心法思考这个问题,如果第一个人选的数字已经确定了,那么第二个人肯定会遍历整个区间,选出其中乘积最小的对应数字。
对于第一个人来说,他选数的时候其实可以预见第二个人选的数字。
$40$ 分做法:
直接枚举第一个人选的数字,然后遍历区间求出第二个人选的数字,实质是选每行最小值中的最大值,时间复杂度为 $O(nmq)$ 。
当数据满足特殊性质 $2$ 时,时间复杂度为 $O(nq)$ 。
$65$ 分做法:
再考虑到特殊性质 $1$:$A_i, B_i > 0$,不管第一个人选的数字是什么,第二个人选的数字一定是区间中最小的数字。所以,第一个人一定会选区间中最大的数。
我们可以使用 $ST$ 表或者线段树维护 $A$ 数组的区间最大值和 $B$ 数组的区间最小值,然后对于满足特殊性质 $1$ 的点,答案一定是 $A$ 数组指定区间的最大值 $\times$ $B$ 数组指定区间的最小值。
$100$ 分做法:
按照上述讨论,如果 $A_i, B_i$ 都大于 $0$,那么取的数字一定是区间最值。拓展上述结论会发现:如果第一个人取的是正数,第二个人一定会取区间的最小值;如果第一个人取的是负数,第二个人一定会取区间最大值。
在此基础上考虑第一个人的取值
- 如果他取正数:当第二个人取的区间最小值是正数时,第一个人应该取最大的正数;如果第二个人取的区间最小值是负数时,第一个人应该取最小的正数(或者有 $0$ 取 $0$);
- 如果他取负数:当第二个人取的区间最大值是正数时,第一个人应该取最大的负数;如果第二个人取的区间最小值是负数,第一个人应该取最小的负数。
综上,第一个人只会取区间中四种数中的一个:最小的负数、最大的负数、最小的非负数、最大的非负数;而第二个人只会根据第一个人取的数的符号取区间的最大值或最小值。
使用 $ST$ 表,维护 $A$ 数组的区间最大负数、区间最小负数、区间最大非负数、区间最小非负数,再维护 $B$ 数组的区间最大和区间最小,然后每轮游戏只有四种方案,求出其中最大值就能得出这一轮的答案了。
C++ 代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxs = 20;
const int maxn = 100005;
const ll INF = 1e18;
int n, m, q, num[maxn];
struct Node {
ll neg_mn, neg_mx;
ll pos_mn, pos_mx;
Node(ll neg_mn=0, ll neg_mx=0, ll pos_mn=0, ll pos_mx=0) : neg_mn(neg_mn), neg_mx(neg_mx), pos_mn(pos_mn), pos_mx(pos_mx) {};
Node operator | (Node nxt) {
return Node(min(neg_mn, nxt.neg_mn),
max(neg_mx, nxt.neg_mx),
min(pos_mn, nxt.pos_mn),
max(pos_mx, nxt.pos_mx));
}
} ST[2][maxn][maxs];
Node query(int flag, int l, int r) {
int t = num[r-l+1];
return ST[flag][l][t] | ST[flag][r-(1<<t)+1][t];
}
int main() {
scanf("%d%d%d", &n, &m, &q);
for (int i = 2; i <= max(n, m); ++i) num[i] = num[i>>1] + 1;
ll x;
for (int i = 1; i <= n; ++i) {
scanf("%lld", &x);
ST[0][i][0] = x > 0 ? Node(0, -INF, x, x) : Node(x, x, INF, 0);
}
for (int i = 1; i <= m; ++i) {
scanf("%lld", &x);
ST[1][i][0] = x > 0 ? Node(0, -INF, x, x) : Node(x, x, INF, 0);
}
for (int k = 0; k <= 1; ++k) {
for (int j = 1; j < maxs; ++j) {
int lim = k == 0 ? n : m;
for (int i = 1; i + (1 << j) - 1 <= lim; ++i) {
ST[k][i][j] = ST[k][i][j-1] | ST[k][i + (1<<(j - 1))][j-1];
}
}
}
for (int i = 1; i <= q; ++i) {
int l1, r1, l2, r2;
scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
Node a = query(0, l1, r1), b = query(1, l2, r2);
if (b.neg_mx == -INF) {
printf("%lld\n", a.pos_mn == INF ? a.neg_mx*b.pos_mx : a.pos_mx*b.pos_mn);
}
else if (b.pos_mn == INF) {
printf("%lld\n", a.neg_mx == -INF ? a.pos_mn*b.neg_mn : a.neg_mn*b.neg_mx);
}
else {
printf("%lld\n", max(a.neg_mx == -INF ? -INF : a.neg_mx*b.pos_mx, a.pos_mn == INF ? -INF : a.pos_mn*b.neg_mn));
}
}
return 0;
}