2022 策略游戏 · 方案二 ST 表区间极值

CSP-S 标程 · 复赛真题 · 代码 · cpp · 难度 4/5 · 共 4021 字
ST 表查区间极值，A 方的最优反应只有四种
2022
ST表
正文

// CSP-S 2022 复赛 T2 · 策略游戏（方案二：ST 表区间极值，满分 O((n+m)log + q·c)）
// 原题：https://oj.yecheng.tv/p/CSPS2022B
// 题意：同方案一（n, m, q ≤ 1e5，需满分）。
// 思路（L1 的最优反应只有四种）：
//   固定 a 后 L1 取 max(a·b) —— b ∈ B 段，只需 B 段的：
//   最小负数（a>0 时最小）、最大正数（a<0 时最小）、0（存在则 0）、
//   最大正 / 最小负的绝对值组合。等价地：预计算 B 段四个值：
//   bmin（最小）、bmax（最大）、以及"是否存在 0"。
//   a 的最优选择同理只需要 A 段的四类候选：amin、amax、0（若存在）、
//   以及"绝对值最小的负数 / 正数"（避免被 b 放大成大数）。
//   严谨做法：答案 = min over a-candidates of max over b-candidates。
//   侯选 a：A 段的最大正、最小正、最大负、最小负（4 个 ST 表）；
//   b 候选同理 4 个。4×4 组合取 min-max 即可（0 特判：若 A 有 0，
//   a=0 时结果 = 0·max(b)？= 0——但 max(b·0)=0，是 L0 的强候选）。
//   用 ST 表维护 8 个量：A/B 各自的 [最小负、最大负、最小正、最大正]
//   + 是否含 0。每询问 O(log) × 常数。
// 复杂度：预处理 O((n+m) log)，每询问 O(16)。
// 易错点：
//   1. 0 的影响：b 段含 0 → a>0 时 L1 至多得 0（选 b=0）；
//   2. 负负得正：a<0 时 L1 选 bmin（最负）得最大正积；
//   3. 8 个 ST 表逐一分清符号区间；
//   4. 全程 long long。
#include <cstdio>
#include <algorithm>
using namespace std;

const long long INF = 4e18;
int n, m, q;
long long A[100005], B[100005];
// st[kind][k][i]：kind 0=A/1=B；k: 0 最小负 1 最大负 2 最小正 3 最大正
long long st[2][4][17][100005];
bool hasZero[2][17][100005];
int lg[100005];

void build(long long* a, int len, int kind) {
    for (int i = 1; i <= len; i++) {
        long long v = a[i];
        // 初始化 4 类
        st[kind][0][0][i] = (v < 0) ? v : INF;
        st[kind][1][0][i] = (v < 0) ? v : -INF;
        st[kind][2][0][i] = (v > 0) ? v : INF;
        st[kind][3][0][i] = (v > 0) ? v : -INF;
        hasZero[kind][0][i] = (v == 0);
    }
    for (int j = 1; (1 << j) <= len; j++)
        for (int i = 1; i + (1 << j) - 1 <= len; i++) {
            for (int k = 0; k < 4; k++) {
                long long x = st[kind][k][j - 1][i];
                long long y = st[kind][k][j - 1][i + (1 << (j - 1))];
                st[kind][k][j][i] = (k < 2) ? max(x, y) : min(x, y);
                // 注意：最小负 = 负数里最小的 → min；最大负 → max
                if (k == 0) st[kind][k][j][i] = min(x, y);
                if (k == 1) st[kind][k][j][i] = max(x, y);
                if (k == 2) st[kind][k][j][i] = min(x, y);
                if (k == 3) st[kind][k][j][i] = max(x, y);
            }
            hasZero[kind][j][i] = hasZero[kind][j - 1][i] || hasZero[kind][j - 1][i + (1 << (j - 1))];
        }
}

// 返回 [l,r] 的 4 个候选（负数最大/最小、正数最大/最小），zero 标记
void query(int kind, int l, int r, long long out[4], bool& zero) {
    int j = lg[r - l + 1];
    zero = hasZero[kind][j][l] || hasZero[kind][j][r - (1 << j) + 1];
    for (int k = 0; k < 4; k++) {
        long long x = st[kind][k][j][l];
        long long y = st[kind][k][j][r - (1 << j) + 1];
        if (k == 0 || k == 2) out[k] = min(x, y);
        else out[k] = max(x, y);
    }
}

int main() {
    freopen("game.in", "r", stdin);
    freopen("game.out", "w", stdout);
    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]);
    lg[1] = 0;
    for (int i = 2; i <= 100000; i++) lg[i] = lg[i / 2] + 1;
    build(A, n, 0);
    build(B, m, 1);
    while (q--) {
        int l1, r1, l2, r2;
        scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
        long long ca[4], cb[4];
        bool za, zb;
        query(0, l1, r1, ca, za);
        query(1, l2, r2, cb, zb);
        long long ans = INF;
        bool first = true;
        for (int i = 0; i < 4; i++) {
            if (ca[i] == INF || ca[i] == -INF) continue;
            long long worst = -INF;
            bool f2 = true;
            for (int j = 0; j < 4; j++) {
                if (cb[j] == INF || cb[j] == -INF) continue;
                long long cur = ca[i] * cb[j];
                if (zb && cur > 0) cur = 0;    // B 段有 0，正积可压到 0
                if (f2 || cur > worst) {
                    worst = cur;
                    f2 = false;
                }
            }
            if (zb && worst > 0) worst = 0;
            if (first || worst < ans) {
                ans = worst;
                first = false;
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}
2022 策略游戏 · 方案二 ST 表区间极值

正文

CSP-S 标程 · 复赛真题的其它内容
