2022 CCF CSP-S2.策略游戏

题目

4733. 策略游戏

算法标签: $ST$表, 线段树

思路

可以求每一行的最小值, 第一个人从每一行最小值选择最大的一个, 但是行和列的数量是$10^5$级别, 因此不能直接创建矩阵进行维护, 当第一个人选定某一行$x$后确定了, 但是$B$希望选择最小的, 需要考虑$A_x$的正负性, 如果$A_x$是正数, 需要在$B_y$中选择最小值, 目标值是$B_{min}\times A_x$, 对于第一个人来说, 如果想要求最大值, 还需要分析$B_{min}$的正负性

总结来说对于如果$A_x$的所有取值都是正数数, 因为$A$是绝顶聪明的, 是知道$B$取最小值的, 因此对于$A$来说最后的得分需要取决于$B_{min}$的正负性

如果第一个人从负数里面选, 因为$A$是决定聪明的, 因此是知道第二个人一定取值是$B_{max}$, 还是取决于$B_{max}$的正负性

将问题总结为

• 求$A$的某个区间的非负整数的最小值
• 求$A$的某个区间的非负整数的最大值
• 求$A$的某个区间负数的最小值
• 求$A$的某个区间负数的最大值
• 求$B$的某个区间的最小值
• 求$B$的某个区间的最大值

直接开$6$个线段树或者$ST$表求解

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>using namespace std;typedef long long LL;
const int N = 100010, INF = 2e9 + 10;
const LL LL_INF = 5e18;int n, m, q;
int a[N], b[N];
struct Node {int l, r, val;
} tr[6][N << 2];int get(int u, int type) {if (type == 0) return a[u] >= 0 ? a[u] : INF;      // A中非负的最小值if (type == 1) return a[u] >= 0 ? a[u] : -INF;     // A中非负的最大值if (type == 2) return a[u] < 0 ? a[u] : INF;       // A中负数的最小值if (type == 3) return a[u] < 0 ? a[u] : -INF;      // A中负数的最大值return b[u];                                       // B数组的值
}void push_up(Node tr[], int u, int type) {int l_val = tr[u << 1].val, r_val = tr[u << 1 | 1].val;// 偶数求最小值if (type % 2 == 0) tr[u].val = min(l_val, r_val);// 奇数求最大值else tr[u].val = max(l_val, r_val);
}void build(Node tr[], int u, int l, int r, int type) {tr[u] = {l, r};if (l == r) {tr[u].val = get(r, type);return;}int mid = l + r >> 1;build(tr, u << 1, l, mid, type);build(tr, u << 1 | 1, mid + 1, r, type);push_up(tr, u, type);
}int query(Node tr[], int u, int ql, int qr, int type) {if (tr[u].l >= ql && tr[u].r <= qr) return tr[u].val;int mid = tr[u].l + tr[u].r >> 1;// 查询最小值if (type % 2 == 0) {int ans = INF;if (ql <= mid) ans = min(ans, query(tr, u << 1, ql, qr, type));if (qr > mid) ans = min(ans, query(tr, u << 1 | 1, ql, qr, type));return ans;}// 查询最大值int ans = -INF;if (ql <= mid) ans = max(ans, query(tr, u << 1, ql, qr, type));if (qr > mid) ans = max(ans, query(tr, u << 1 | 1, ql, qr, type));return ans;
}int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> n >> m >> q;for (int i = 1; i <= n; ++i) cin >> a[i];for (int i = 1; i <= m; ++i) cin >> b[i];for (int i = 0; i < 4; ++i) build(tr[i], 1, 1, n, i);for (int i = 4; i < 6; ++i) build(tr[i], 1, 1, m, i);while (q--) {int l1, r1, l2, r2;cin >> l1 >> r1 >> l2 >> r2;// 查询B数组的最小值和最大值int y_min = query(tr[4], 1, l2, r2, 4);int y_max = query(tr[5], 1, l2, r2, 5);LL x, ans = -LL_INF;// B的最小值非负时，A应选择最大的非负数if (y_min >= 0) x = query(tr[1], 1, l1, r1, 1);else x = query(tr[0], 1, l1, r1, 0);if (abs(x) != INF) ans = max(ans, x * (LL)y_min);// B的最大值非负时，A应选择最大的负数if (y_max >= 0) x = query(tr[3], 1, l1, r1, 3);else x = query(tr[2], 1, l1, r1, 2);if (abs(x) != INF) ans = max(ans, x * (LL)y_max);cout << ans << "\n";}return 0;
}