P8818 策略游戏 Sol

有一个人先手，肯定要选择使得最坏情况最优的点。

考虑分讨区间内元素情况。

1. \(a\) 为自然数，\(b\) 为自然数。

先手选择 \(\max\)，后手选择 \(\min\)。

2. \(a\) 为自然数，\(b\) 为负数。

先手选择 \(\min\)，后手选择 \(\min\)。因为先手如选择 \(\max\)，则后手选 \(\min\) 会使答案更小。

3. \(a\) 为自然数，\(b\) 无特殊限制。

同 2 情况。

4. \(a\) 为负数，\(b\) 为自然数。

先手选择 \(\max\)，后手选择 \(\max\)。要使得负数 \(\times\) 正数最大，先手需要让负数绝对值更小，后手则贪心地选择让乘积更小，选择区间最大值。

5. \(a\) 为负数，\(b\) 为负数。

这时候负负得正，先手选择 \(\min\) 会让后手被迫选择 \(\max\)。原因显然。

6. \(a\) 为负数，\(b\) 无特殊限制。

显然后手要选自然数，那么先手选择 \(\max\)。

7. \(a\) 无特殊限制，\(b\) 为自然数。

先手显然选 \(\max\)，后手显然选 \(\min\)。

8. \(a\) 无特殊限制，\(b\) 为负数。

先手显然选 \(\min\)，后手选 \(\max\)，负负得正，乘积最小。

9. \(a\) 无特殊限制，\(b\) 无特殊限制。

考虑两种情况，若先手选最小的自然数，则后手会选最小的负数来回应。

若先手选最大的负数，则后手会选择最大的自然数来回应。

取 \(\max\) 即可。

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 1e5 + 10, Log = 20, inf = 1e9;
int n, m, q, lg[N], bn[Log];
ll a[N], b[N], Min[3][Log][N], Max[3][Log][N];

inline ll queryMin(int typ, int l, int r) {
	int k = lg[r - l + 1];
	return min(Min[typ][k][l], Min[typ][k][r - bn[k] + 1]);
} inline ll queryMax(int typ, int l, int r) {
	int k = lg[r - l + 1];
	return max(Max[typ][k][l], Max[typ][k][r - bn[k] + 1]);
}

inline void solve() {
	int l1, r1, l2, r2; scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
	ll Min1 = queryMin(0, l1, r1), Max1 = queryMax(0, l1, r1);
	ll Min2 = queryMin(1, l2, r2), Max2 = queryMax(1, l2, r2);
	ll ans = 0;
	if (Min1 >= 0) {
		if (Min2 >= 0) ans = Max1 * Min2;
		else if (Max2 < 0) ans = Min1 * Min2;
		else ans = Min1 * Min2;
	} else if (Max1 < 0) {
		if (Min2 >= 0) ans = Max1 * Max2;
		else if (Max2 < 0) ans = Min1 * Max2;
		else ans = Max1 * Max2;
	} else {
		if (Min2 >= 0) ans = Max1 * Min2;
		else if (Max2 < 0) ans = Min1 * Max2;
		else {
			ll fi = queryMin(2, l1, r1), se = queryMax(2, l1, r1);
			ans = max(fi * Min2, se * Max2);
		}
	}
	printf("%lld\n", ans); return ;
}

int main() {
	scanf("%d%d%d", &n, &m, &q);
	for (int i = 1; i <= n; ++i) scanf("%lld", &a[i]);
	for (int i = 1; i <= m; ++i) scanf("%lld", &b[i]);
	bn[0] = 1; for (int i = 1; i < Log; ++i) bn[i] = bn[i - 1] << 1;
	lg[0] = -1; for (int i = 1; i < N; ++i) lg[i] = lg[i >> 1] + 1;
	for (int i = 1; i <= n; ++i) Min[0][0][i] = Max[0][0][i] = a[i];
	for (int i = 1; i < Log; ++i)
	  for (int j = 1; j + bn[i] - 1 <= n; ++j) {
	  	Min[0][i][j] = min(Min[0][i - 1][j], Min[0][i - 1][j + bn[i - 1]]);
	  	Max[0][i][j] = max(Max[0][i - 1][j], Max[0][i - 1][j + bn[i - 1]]);
		}
	for (int i = 1; i <= m; ++i) Min[1][0][i] = Max[1][0][i] = b[i];
	for (int i = 1; i < Log; ++i)
	  for (int j = 1; j + bn[i] - 1 <= m; ++j) {
		  Min[1][i][j] = min(Min[1][i - 1][j], Min[1][i - 1][j + bn[i - 1]]);
		  Max[1][i][j] = max(Max[1][i - 1][j], Max[1][i - 1][j + bn[i - 1]]);
	  }
  for (int i = 1; i <= n; ++i) {
  	if (a[i] >= 0) Min[2][0][i] = a[i]; else Min[2][0][i] = inf;
  	if (a[i] < 0) Max[2][0][i] = a[i]; else Max[2][0][i] = -inf;
	}
	for (int i = 1; i < Log; ++i)
	  for (int j = 1; j + bn[i] - 1 <= n; ++j) {
	  	Min[2][i][j] = min(Min[2][i - 1][j], Min[2][i - 1][j + bn[i - 1]]);
	  	Max[2][i][j] = max(Max[2][i - 1][j], Max[2][i - 1][j + bn[i - 1]]);
		}
  while (q--) solve();
  return 0;
}

原文地址：http://www.cnblogs.com/MistZero/p/P8818-Sol.html