「CSP-S 2022」策略游戏 - 贪心 + 线段树

发表于 更新于 分类于 ， 阅读次数： Disqus：

题意描述

洛谷链接

LibreOJ 链接

小 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 的目标是使得这个得分尽可能小。同时两人都是足够聪明的玩家，每次都会采用最优的策略。

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

对于所有数据，\(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\)。

解题思路

本题显然可贪心解决。

由于小 L 先抽，小 Q 后抽，由于小 L 先抽时必须考虑小 Q 可选的情况，于是我们可以先看小 Q 可以抽什么。假设小 L 选了 \(x\)，若 \(x > 0\)，则小 Q 选得尽量小；若 \(x \le 0\)，则小 Q 选得尽量大即可。

接下来考虑小 L 的情况。设小 Q 可选的最小数为 \(\text{minB}\)，最大数为 \(\text{maxB}\)：

  • 若 \(\text{minB}\)、\(\text{maxB}\) 异号：则只要不选 \(0\)，得到的数始终为负数。这种情况能选 \(0\) 就选 \(0\)；如果没有 \(0\) 就在选择正数最小值或负数最大值两种情况中取最优情况即可。
  • 若 \(\text{minB}\)、\(\text{maxB}\) 同号：尽量选同号且绝对值最大的数。若没有同号，则选择 \(0\) 以及异号中绝对值最小的数。证明显然。
  • 若 \(\text{minB}\)、\(\text{maxB}\) 中至少有一个为 \(0\)：同上。

于是我们可以开线段树维护 \(A\) 的最大值、最小值、正数最小值、负数最大值和 \(0\) 的个数以及维护 \(B\) 的最大值和最小值。对于每次询问查询后分类讨论即可。

最后注意一下 \(l1 = r1\) 或 \(l2 = r2\) 时特判一下即可。时间复杂度 \(O(n \log n)\)

代码演示

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

const int MAXN = 1e5;

struct SegTMin {
    int l, r;
    SegTMin *lc, *rc;
    long long val;

    SegTMin(int l, int r, SegTMin *lc, SegTMin *rc) : l(l), r(r), lc(lc), rc(rc) {}
    SegTMin(int l, int r, SegTMin *lc, SegTMin *rc, long long val) : l(l), r(r), lc(lc), rc(rc), val(val) {}

    long long query(const int l, const int r) {
        if (l > this->r || r < this->l) return INT_MAX;
        else if (l <= this->l && r >= this->r) return val;
        else return std::min(lc->query(l, r), rc->query(l, r));
    }

    static SegTMin *build(const int l, const int r, long long *a) {
        if (l == r) return new SegTMin(l, r, nullptr, nullptr, a[l]);
        else {
            const int mid = l + (r - l) / 2;
            SegTMin *segt = new SegTMin(l, r, build(l, mid, a), build(mid + 1, r, a));
            segt->val = std::min(segt->lc->val, segt->rc->val);
            return segt;
        }
    }
} *segMinA, *segMinB, *segMinPA, *segMinMA;

struct SegTMax {
    int l, r;
    SegTMax *lc, *rc;
    long long val;

    SegTMax(int l, int r, SegTMax *lc, SegTMax *rc) : l(l), r(r), lc(lc), rc(rc) {}
    SegTMax(int l, int r, SegTMax *lc, SegTMax *rc, long long val) : l(l), r(r), lc(lc), rc(rc), val(val) {}

    long long query(const int l, const int r) {
        if (l > this->r || r < this->l) return INT_MIN;
        else if (l <= this->l && r >= this->r) return val;
        else return std::max(lc->query(l, r), rc->query(l, r));
    }

    static SegTMax *build(const int l, const int r, long long *a) {
        if (l == r) return new SegTMax(l, r, nullptr, nullptr, a[l]);
        else {
            const int mid = l + (r - l) / 2;
            SegTMax *segt = new SegTMax(l, r, build(l, mid, a), build(mid + 1, r, a));
            segt->val = std::max(segt->lc->val, segt->rc->val);
            return segt;
        }
    }
} *segMaxA, *segMaxB;

int main() {
    int n, m, q;
    scanf("%d %d %d", &n, &m, &q);

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

    static long long zero[MAXN + 1], pa[MAXN + 1], ma[MAXN + 1];
    for (int i = 1; i <= n; i++) {
        if (a[i] > 0) pa[i] = a[i], ma[i] = INT_MAX;
        if (a[i] < 0) ma[i] = -a[i], pa[i] = INT_MAX;
        zero[i] = zero[i - 1] + (a[i] == 0);
    }

    segMinA = SegTMin::build(1, n, a);
    segMaxA = SegTMax::build(1, n, a);
    segMinB = SegTMin::build(1, m, b);
    segMaxB = SegTMax::build(1, m, b);
    segMinPA = SegTMin::build(1, n, pa);
    segMinMA = SegTMin::build(1, n, ma);

    while (q--) {
        long long ans = 0;
        int l1, r1, l2, r2;
        scanf("%d %d %d %d", &l1, &r1, &l2, &r2);

        long long minA = segMinA->query(l1, r1);
        long long maxA = segMaxA->query(l1, r1);
        long long minB = segMinB->query(l2, r2);
        long long maxB = segMaxB->query(l2, r2);

        if (l1 == r1) {
            if (a[l1] > 0) ans = minB * a[l1];
            else ans = maxB * a[l1];
        } else if (l2 == r2) {
            if (b[l2] > 0) ans = maxA * b[l2];
            else ans = minA * b[l2];
        } else {
            if (minB * maxB > 0) {
                if (minB >= 0) {
                    if (maxA < 0) ans = maxA * maxB;
                    else ans = maxA * minB;
                } else {
                    if (minA < 0) ans = minA * maxB;
                    else ans = minA * minB;
                }
            } else if (minB * maxB == 0) {
                if (minB == 0) {
                    if (maxA < 0) ans = maxA * maxB;
                    else ans = 0;
                } else {
                    if (minA < 0) ans = 0;
                    else ans = minA * minB;
                }
            } else if (minB * maxB < 0) {
                if (zero[r1] - zero[l1 - 1] > 0) {
                    ans = 0;
                } else {
                    long long npa = segMinPA->query(l1, r1);
                    long long nma = segMinMA->query(l1, r1);
                    ans = std::max(npa * minB, -nma * maxB);
                }
            }
        }

        printf("%lld\n", ans);
    }

    return 0;
}