洛谷 P8818 策略游戏 - Solution

1. 题目数据 (Problem Metadata)

• 题目类型：传统题
• 题目链接：P8818 [CSP-S 2022] 策略游戏 - 洛谷
• 时间限制：1.00s
• 内存限制：512.00MB

2. 题意简述 (Problem Summary)

给定长度为 $n$ 的数组 $A$ 和长度为 $m$ 的数组 $B$（$1 \le n, m, q \le 10^5$，$|a_i|, |b_i| \le 10^9$）。共 $q$ 轮游戏，每轮给定 $l_1, r_1, l_2, r_2$：小 L 先从 $A[l_1..r_1]$ 中选一个数 $a$，小 Q 再从 $B[l_2..r_2]$ 中选一个数 $b$。小 L 要让 $a \cdot b$ 尽可能大，小 Q 要让 $a \cdot b$ 尽可能小。求每轮在双方最优策略下的乘积值：

$$\text{ans} = \max_{a \in A[l_1..r_1]}\; \min_{b \in B[l_2..r_2]}\; a \cdot b$$

3. 朴素解法 (Brute-Force)

最直接的想法是对每个查询枚举 $A[l_1..r_1]$ 中每个 $a$，对每个 $a$ 枚举 $B[l_2..r_2]$ 中每个 $b$ 计算 $a \cdot b$ 取最小值，再对 $a$ 取最大值。

• 每次查询需 $O\big((r_1-l_1+1)(r_2-l_2+1)\big)$，最坏 $O(nm)$。
• $q$ 次查询总计 $O(qnm) \approx 10^{15}$，完全不可行。

即使优化为「先扫描 $B$ 求得 $b_{\min}, b_{\max}$，再枚举 $A$ 中每个 $a$ 根据 $a$ 的符号选 $b_{\min}$ 或 $b_{\max}$」，每次查询仍需 $O(n+m)$，总计 $O\big(q(n+m)\big) \approx 2 \times 10^{10}$，仍然超时。瓶颈在于每次查询都要重新扫描数组求极值。

4. 核心解法 (Main Solution)

特殊性质

这是一个 min-max 博弈：小 L 先手最大化，小 Q 后手最小化。关键观察在于，给定小 L 选定的 $a$ 后，小 Q 的最优选择只取决于 $a$ 的符号，而与 $B$ 区间的正负组成无关。

关键突破

固定 $a$，小 Q 要选 $b$ 使 $a \cdot b$ 最小：

• 若 $a > 0$：$a \cdot b$ 随 $b$ 单调递增，小 Q 选 $b_{\min}$。
• 若 $a < 0$：$a \cdot b$ 随 $b$ 单调递减，小 Q 选 $b_{\max}$。
• 若 $a = 0$：乘积恒为 $0$。

因此无论 $B$ 区间是全正、全负还是混合，小 Q 的选择都统一为「$a$ 负选 $b_{\max}$，$a$ 正选 $b_{\min}$」。这就是为什么代码只需要维护 $B$ 的区间最大值与最小值，而不必像后文分析 $A$ 那样细分 $B$ 的正负。

下面分析小 L 的选数策略。定义小 L 选定 $a$ 后的最终结果为：

$$g(a) = \begin{cases} a \cdot b_{\min} & a > 0 \\ a \cdot b_{\max} & a < 0 \\ 0 & a = 0 \end{cases}$$

小 L 要求 $\max g(a)$。注意到 $g(a)$ 在 $a > 0$ 和 $a < 0$ 两段上分别是关于 $a$ 的线性函数（系数 $b_{\min}$ 或 $b_{\max}$ 固定），而线性函数在区间上的最大值只在端点取得。因此小 L 只需考虑 $A$ 区间中的几个极值候选。接下来我们推导各种选择时的结果，以及选择策略。

推导过程

之所以正数和负数各取两个端点，是因为 $b_{\min}$、$b_{\max}$ 的符号事先未知：当 $b_{\min} > 0$ 时正数段越大越好（选 $a_p^{\max}$），当 $b_{\min} < 0$ 时正数段越小越好（选 $a_p^{\min}$）；负数段同理。把所有存在的候选算一遍取 $\max$，即可覆盖所有情况。

至此问题归结为 $O(1)$ 查询 $A$ 的上述极值与 $B$ 的 $b_{\min}, b_{\max}$，用 ST 表 预处理即可。小 L 会在这些所有候选结果中选出一个最大的作为答案。

5. 正确性证明 (Proof of Correctness)

需证两点：小 Q 的最优策略，以及小 L 的候选集充分性。

引理（小 Q 的最优选择）：设小 L 已选 $a$，小 Q 在 $B$ 中选 $b$ 使 $a \cdot b$ 最小。当 $a > 0$ 时 $a \cdot b$ 关于 $b$ 单调递增，最小值在 $b = b_{\min}$ 取得；当 $a < 0$ 时关于 $b$ 单调递减，最小值在 $b = b_{\max}$ 取得；当 $a = 0$ 时乘积恒为 $0$。这与 $b_{\min}, b_{\max}$ 本身的正负无关，因为 $b_{\min}$ 始终是 $B$ 中最小的、$b_{\max}$ 始终是最大的。

定理（小 L 候选集充分性）：小 L 的最优 $a$ 一定在 $\{a_p^{\max}, a_p^{\min}, a_n^{\max}, a_n^{\min}, 0\}$（若存在）之中。对于 $a > 0$ 的部分，$g(a) = a \cdot b_{\min}$ 是关于 $a$ 的一次函数，$b_{\min}$ 为常数，一次函数在区间上的最大值在端点取得，故只需检查最小正数与最大正数。$a < 0$ 的部分，$g(a) = a \cdot b_{\max}$ 同理只需检查最小负数与最大负数。$a = 0$ 时 $g(0) = 0$。三类候选的并集不重不漏地覆盖了 $a$ 的所有取值，取 $\max$ 即得全局最优。

综上所述，算法正确。

6. 复杂度分析 (Complexity)

• 时间复杂度：$O\big((n+m) \log n + q\big)$。ST 表建表 $5$ 个 $A$ 表加 $2$ 个 $B$ 表，每个 $O(n \log n)$，约 $7 \times 10^5 \times 17 \approx 1.2 \times 10^7$ 次运算；每次查询 $O(1)$，$q$ 次共 $10^5$。1s 时限内轻松通过。
• 空间复杂度：$O(n \log n)$。$7$ 个 ST 表，每个表 $10^5 \times 20 \times 8$ 字节 $\approx 16$ MB，共约 $112$ MB，低于 $512$ MB 限制。

7. 实现细节与避坑指南 (Implementation Details)

8. 参考代码 (Reference Code)

下面是我按「先分析小 L 的选数策略，再推导小 Q 的最优反应」这一直觉顺序写出的 ST 表解法。维护 $A$ 的五个区间量（最大/最小正数、最大/最小负数、是否含 $0$）与 $B$ 的最大/最小值，每次查询枚举四个极值候选加 $0$ 取 $\max$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102

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

const int N = 1e5 + 5, inf = 2e9;

int n, m, q;

int a[N], b[N];

int a_max_p[N][20], a_min_p[N][20], a_min_n[N][20], a_max_n[N][20];
int b_max[N][20], b_min[N][20];
int a_0[N][20];

int lg2[N];

#define pow2(x) (1<<(x))

void ST_init() {
    for (int i = 1;i <= n;i++) {
        a_max_p[i][0] = max(a[i], 0LL);
        a_min_p[i][0] = ((a[i] > 0) ? a[i] : inf);
        a_max_n[i][0] = ((a[i] < 0) ? a[i] : -inf);
        a_min_n[i][0] = min(a[i], 0LL);
        a_0[i][0] = (a[i] == 0);
    }
    for (int j = 1;j <= lg2[n];j++) {
        for (int i = 1;i + pow2(j) - 1 <= n;i++) {
            a_max_p[i][j] = max(a_max_p[i][j - 1], a_max_p[i + pow2(j - 1)][j - 1]);
            a_min_p[i][j] = min(a_min_p[i][j - 1], a_min_p[i + pow2(j - 1)][j - 1]);
            a_max_n[i][j] = max(a_max_n[i][j - 1], a_max_n[i + pow2(j - 1)][j - 1]);
            a_min_n[i][j] = min(a_min_n[i][j - 1], a_min_n[i + pow2(j - 1)][j - 1]);
            a_0[i][j] = a_0[i][j - 1] | a_0[i + pow2(j - 1)][j - 1];
        }
    }
    for (int i = 1;i <= m;i++) {
        b_max[i][0] = b_min[i][0] = b[i];
    }
    for (int j = 1;j <= lg2[m];j++) {
        for (int i = 1;i + pow2(j) - 1 <= m;i++) {
            b_max[i][j] = max(b_max[i][j - 1], b_max[i + pow2(j - 1)][j - 1]);
            b_min[i][j] = min(b_min[i][j - 1], b_min[i + pow2(j - 1)][j - 1]);
        }
    }
}

int ST_query_max(int st[][20], int l, int r) {
    int k = lg2[r - l + 1];
    return max(st[l][k], st[r - pow2(k) + 1][k]);
}

int ST_query_min(int st[][20], int l, int r) {
    int k = lg2[r - l + 1];
    return min(st[l][k], st[r - pow2(k) + 1][k]);
}

signed main() {
    // Don't stop. Don't hide. Follow the light, and you'll find tomorrow.

    scanf("%lld %lld %lld\n", &n, &m, &q);
    for (int i = 2;i <= 100000;i++) {
        lg2[i] = lg2[i / 2] + 1;
    }

    for (int i = 1;i <= n;i++) scanf("%lld ", &a[i]);
    for (int i = 1;i <= m;i++) scanf("%lld ", &b[i]);

    ST_init();

    for (int i = 1;i <= q;i++) {
        int l1, r1, l2, r2;
        scanf("%lld %lld %lld %lld\n", &l1, &r1, &l2, &r2);
        int ans = -2e18, L, Q;
        if (ST_query_max(a_0, l1, r1)) ans = 0;
        // L 选一个最小的负数
        L = ST_query_min(a_min_n, l1, r1);
        if (L < 0 && L != -inf) {
            Q = ST_query_max(b_max, l2, r2);
            ans = max(ans, L * Q);
        }
        // L 选一个最大的正数
        L = ST_query_max(a_max_p, l1, r1);
        if (L > 0 && L != inf) {
            Q = ST_query_min(b_min, l2, r2);
            ans = max(ans, L * Q);
        }
        // L 选一个最大的负数
        L = ST_query_max(a_max_n, l1, r1);
        if (L < 0 && L != -inf) {
            Q = ST_query_max(b_max, l2, r2);
            ans = max(ans, L * Q);
        }
        // L 选一个最小的正数
        L = ST_query_min(a_min_p, l1, r1);
        if (L > 0 && L != inf) {
            Q = ST_query_min(b_min, l2, r2);
            ans = max(ans, L * Q);
        }
        printf("%lld\n", ans);
    }
    return 0;
}

9. 补充说明 (Additional Notes)

• 题目渊源：本题出自 CSP-S 2022 第二轮 第二题，是「min-max 博弈 + ST 表」的经典结合。这类「先手最大化、后手最小化」的零和博弈在竞赛中很常见，核心识别信号是双层 $\max\text{-}\min$ 嵌套——出现时先固定先手选择，分析后手的最优反应函数，往往能将后手的连续选择域压缩到少数极值上。
• 思路与代码的简化：我在初步分析时曾想细分 $B$ 区间的正负组成（只含负数、只含正数、含 $0$、正负混合），对应维护 $B$ 的最大正数、最大非正数、最小负数、最小非负数。但推导后发现，小 Q 的最优 $b$ 选择只取决于 $a$ 的符号——$a$ 负选 $b_{\max}$，$a$ 正选 $b_{\min}$——与 $B$ 的正负组成无关。因此代码只需要 $b_{\max}$ 和 $b_{\min}$ 两个量，初步分析中的复杂分类是推导过程的中间产物，最终被统一掉了。这种「分析时多想几步、实现时只保留必要部分」是常见的解题节奏。ST 表作为静态区间极值查询的经典工具，在这类需要 $O(1)$ 查询多个极值的问题中几乎是首选，方法经典，有学习的价值。
• 其他方法：线段树等区间数据结构也可以解决 RMQ 问题，但在此类场景中 ST 表更优。