[CSP-S 2022] 策略游戏

GitHub 跳转原题关系图返回列表

把极大极小乘积按 B 区间符号分三类讨论，只需在 A 区间查询最值、最小正数、最大负数和是否有零。

OJ: luogu

题目 ID: P8818

难度:提高+/省选-

标签:ST表分类讨论极小化极大思维

日期: 2026-06-21 14:48

题意

有两个数组 A、B。

每次询问给出两个区间：

A[l1..r1]
B[l2..r2]

小 L 先从 A 的区间里选一个数，小 Q 再从 B 的区间里选一个数。
得分是这两个数的乘积。

小 L 想让得分尽量大，小 Q 想让得分尽量小。
要求输出双方都最优时的得分。

思路

先看一个可以直接验证想法的朴素解：

cpp

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#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int n, m, q;
ll a[205], b[205];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= m; i++) {
        cin >> b[i];
    }

    while (q--) {
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;

        // brute.cpp：枚举小 L 选哪个 x，再枚举小 Q 选哪个 y，直接按题意做极大极小。
        ll answer = -(1LL << 60);
        for (int x = l1; x <= r1; x++) {
            ll worst = (1LL << 60);
            for (int y = l2; y <= r2; y++) {
                worst = min(worst, a[x] * b[y]);
            }
            answer = max(answer, worst);
        }
        cout << answer << '\n';
    }

    return 0;
}

暴力做法就是枚举小 L 选哪个 A_x，再枚举小 Q 选哪个 B_y，求出每个 x 对应的最坏结果，然后再取最大值。这个方法复杂度是 $O(|A区间| * |B区间|)$ ，完全不够。

关键是先固定小 L 选到的一个数 a，思考小 Q 会怎么选：

如果 a > 0，为了让乘积尽量小，小 Q 一定会选 B 区间里的最小值
如果 a < 0，小 Q 一定会选 B 区间里的最大值
如果 a = 0，结果恒为 0

所以一轮查询里，B 区间真正有用的信息只有：

最小值 minB
最大值 maxB

然后按 B 区间的符号分三类讨论。

1. `B` 区间全非负

这时：

正数 a 的得分是 a * minB
负数 a 的得分是 a * maxB

为了让结果尽量大：

如果 A 区间里有非负数，显然选最大的 a
否则只能在负数里选最接近 0 的那个负数

2. `B` 区间全非正

这时：

正数 a 的得分是 a * minB，这是负数
负数 a 的得分是 a * maxB，这是非负数

为了让结果尽量大：

如果 A 区间里有负数，选最小的那个负数（绝对值最大）
否则如果有 0，选 0
否则只能选最小正数

3. `B` 区间同时有正有负

这时：

正数 a 会被乘上 minB，结果是负数
负数 a 会被乘上 maxB，结果也是负数
如果 A 区间有 0，那直接选 0 最优

否则只需要比较：

最小正数 * minB
最大负数（最接近 0 的负数）* maxB

于是我们在 A 区间里需要查询的量只有：

最大值
最小值
最小正数
最大负数
是否存在 0

这些都可以用 ST 表和前缀和在 $O(1)$ 查询出来。
B 区间只要查最小值和最大值即可。

代码

cpp

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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 100005;
const ll INF64 = (1LL << 60);

int n, m, q;
ll a[MAXN], b[MAXN];
int lg2_table[MAXN];
int zero_prefix[MAXN];

ll st_a_max[18][MAXN];
ll st_a_min[18][MAXN];
ll st_a_posmin[18][MAXN]; // 区间内最小正数，不存在时为 INF64
ll st_a_negmax[18][MAXN]; // 区间内最大的负数（最接近 0），不存在时为 -INF64

ll st_b_max[18][MAXN];
ll st_b_min[18][MAXN];

ll query_max(ll st[18][MAXN], int l, int r) {
    int k = lg2_table[r - l + 1];
    return max(st[k][l], st[k][r - (1 << k) + 1]);
}

ll query_min(ll st[18][MAXN], int l, int r) {
    int k = lg2_table[r - l + 1];
    return min(st[k][l], st[k][r - (1 << k) + 1]);
}

void build_logs(int limit) {
    lg2_table[1] = 0;
    for (int i = 2; i <= limit; i++) {
        lg2_table[i] = lg2_table[i >> 1] + 1;
    }
}

void build_st_a() {
    for (int i = 1; i <= n; i++) {
        st_a_max[0][i] = a[i];
        st_a_min[0][i] = a[i];
        st_a_posmin[0][i] = (a[i] > 0 ? a[i] : INF64);
        st_a_negmax[0][i] = (a[i] < 0 ? a[i] : -INF64);
        zero_prefix[i] = zero_prefix[i - 1] + (a[i] == 0);
    }

    for (int k = 1; (1 << k) <= n; k++) {
        int len = 1 << k;
        int half = len >> 1;
        for (int i = 1; i + len - 1 <= n; i++) {
            st_a_max[k][i] = max(st_a_max[k - 1][i], st_a_max[k - 1][i + half]);
            st_a_min[k][i] = min(st_a_min[k - 1][i], st_a_min[k - 1][i + half]);
            st_a_posmin[k][i] = min(st_a_posmin[k - 1][i], st_a_posmin[k - 1][i + half]);
            st_a_negmax[k][i] = max(st_a_negmax[k - 1][i], st_a_negmax[k - 1][i + half]);
        }
    }
}

void build_st_b() {
    for (int i = 1; i <= m; i++) {
        st_b_max[0][i] = b[i];
        st_b_min[0][i] = b[i];
    }

    for (int k = 1; (1 << k) <= m; k++) {
        int len = 1 << k;
        int half = len >> 1;
        for (int i = 1; i + len - 1 <= m; i++) {
            st_b_max[k][i] = max(st_b_max[k - 1][i], st_b_max[k - 1][i + half]);
            st_b_min[k][i] = min(st_b_min[k - 1][i], st_b_min[k - 1][i + half]);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= m; i++) {
        cin >> b[i];
    }

    build_logs(max(n, m));
    build_st_a();
    build_st_b();

    while (q--) {
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;

        ll b_min = query_min(st_b_min, l2, r2);
        ll b_max = query_max(st_b_max, l2, r2);

        ll a_max = query_max(st_a_max, l1, r1);
        ll a_min = query_min(st_a_min, l1, r1);
        ll a_posmin = query_min(st_a_posmin, l1, r1);
        ll a_negmax = query_max(st_a_negmax, l1, r1);
        bool has_zero = (zero_prefix[r1] - zero_prefix[l1 - 1] > 0);

        ll answer;

        if (b_min >= 0) {
            // B 区间全非负，小 Q 会取最小的 B。
            if (a_max < 0) {
                answer = a_negmax * b_max;
            }
            else {
                answer = a_max * b_min;
            }
        }
        else if (b_max <= 0) {
            // B 区间全非正，小 Q 会取最大的 B。
            if (a_min > 0) {
                answer = a_posmin * b_min;
            }
            else {
                answer = a_min * b_max;
            }
        }
        else {
            // B 区间同时有正有负。
            if (has_zero) {
                answer = 0;
            }
            else if (a_max < 0) {
                answer = a_negmax * b_max;
            }
            else if (a_min > 0) {
                answer = a_posmin * b_min;
            }
            else {
                ll cand1 = a_posmin * b_min;
                ll cand2 = a_negmax * b_max;
                answer = max(cand1, cand2);
            }
        }

        cout << answer << '\n';
    }

    return 0;
}

复杂度

预处理 ST 表： $O((n+m)\log(n+m))$
每次查询： $O(1)$

总时间复杂度是 $O((n+m+q)\log(n+m))$ 级别，空间复杂度是 $O((n+m)\log(n+m))$ 。

总结

这题本质不是矩阵博弈，而是：

先把“对手会怎么选”压缩成符号分类
再把每种情况需要的区间信息整理成固定几个最值
用 ST 表把这些区间最值做到 $O(1)$ 查询

最关键的是把极大极小问题拆成清楚的分类讨论。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

P8818 [CSP-S 2022] 策略游戏

题目描述

小 L 和小 Q 在玩一个策略游戏。

有一个长度为 $n$ 的数组 $A$ 和一个长度为 $m$ 的数组 $B$ ，在此基础上定义一个大小为 $n \times m$ 的矩阵 $C$ ，满足 $C_{i j} = A_i \times B_j$ 。所有下标均从 $1$ 开始。

游戏一共会进行 $q$ 轮，在每一轮游戏中，会事先给出 $4$ 个参数 $l_1, r_1, l_2, r_2$ ，满足 $1 \le l_1 \le r_1 \le n$ 、 $1 \le l_2 \le r_2 \le m$ 。

游戏中，小 L 先选择一个 $l_1 \sim r_1$ 之间的下标 $x$ ，然后小 Q 选择一个 $l_2 \sim r_2$ 之间的下标 $y$ 。定义这一轮游戏中二人的得分是 $C_{x y}$ 。

小 L 的目标是使得这个得分尽可能大，小 Q 的目标是使得这个得分尽可能小。同时两人都是足够聪明的玩家，每次都会采用最优的策略。

请问：按照二人的最优策略，每轮游戏的得分分别是多少？

输入格式

第一行输入三个正整数 $n, m, q$ ，分别表示数组 $A$ ，数组 $B$ 的长度和游戏轮数。

第二行： $n$ 个整数，表示 $A_i$ ，分别表示数组 $A$ 的元素。

第三行： $m$ 个整数，表示 $B_i$ ，分别表示数组 $B$ 的元素。

接下来 $q$ 行，每行四个正整数，表示这一次游戏的 $l_1, r_1, l_2, r_2$ 。

输出格式

输出共 $q$ 行，每行一个整数，分别表示每一轮游戏中，小 L 和小 Q 在最优策略下的得分。

输入输出样例 #1

输入 #1

text

输出 #1

text

1
20
4

输入输出样例 #2

输入 #2

text

1
2
3
4
5
6
7
86 4 5
3 -1 -2 1 2 0
1 2 -1 -3
1 6 1 4
1 5 1 4
1 4 1 2
2 6 3 4
2 5 2 3

输出 #2

text

说明/提示

【样例解释 #1】

这组数据中，矩阵 $C$ 如下：

\begin{bmatrix} 0 & 0 \\ -3 & 4 \\ 6 & -8 \end{bmatrix}

在第一轮游戏中，无论小 L 选取的是 $x = 2$ 还是 $x = 3$ ，小 Q 都有办法选择某个 $y$ 使得最终的得分为负数。因此小 L 选择 $x = 1$ 是最优的，因为这样得分一定为 $0$ 。

而在第二轮游戏中，由于小 L 可以选 $x = 2$ ，小 Q 只能选 $y = 2$ ，如此得分为 $4$ 。

【样例 #3】

见附件中的 game/game3.in 与 game/game3.ans。

【样例 #4】

见附件中的 game/game4.in 与 game/game4.ans。

【数据范围】

对于所有数据， $1 \le n, m, q \le {10}^5$ ， $-{10}^9 \le A_i, B_i \le {10}^9$ 。对于每轮游戏而言， $1 \le l_1 \le r_1 \le n$ ， $1 \le l_2 \le r_2 \le m$ 。

测试点编号	$n, m, q \le$	特殊条件
$1$	$200$	1, 2
$2$	$200$	1
$3$	$200$	2
$4 \sim 5$	$200$	无
$6$	$1000$	1, 2
$7 \sim 8$	$1000$	1
$9 \sim 10$	$1000$	2
$11 \sim 12$	$1000$	无
$13$	${10}^5$	1, 2
$14 \sim 15$	${10}^5$	1
$16 \sim 17$	${10}^5$	2
$18 \sim 20$	${10}^5$	无

其中，特殊性质 1 为：保证 $A_i, B_i > 0$ 。
特殊性质 2 为：保证对于每轮游戏而言，要么 $l_1 = r_1$ ，要么 $l_2 = r_2$ 。

[CSP-S 2022] 策略游戏

目录

题意

思路

1. B 区间全非负

2. B 区间全非正

3. B 区间同时有正有负

代码

复杂度

总结

一图流解析

1. `B` 区间全非负

2. `B` 区间全非正

3. `B` 区间同时有正有负