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;
}