UMP9同学的代码修改

userId_undefined
Yuilice

2026-08-12 13:52:00

发布于：浙江

12阅读
0回复
0点赞

问题主要集中在区间信息的初始化、合并，以及最终答案的分类讨论上。

首先，minn_z 表示区间内的最小正数，maxn_f 表示区间内的最大负数。叶子结点初始化时，不能直接把 a[l] 同时赋给这两个变量。如果当前数不是正数，就用 M 表示不存在正数；如果当前数不是负数，就用 -M 表示不存在负数。这样合并左右区间时，就可以直接对 minn_z 取 min，对 maxn_f 取 max。
原来的 flag 只能判断整个数组中是否出现过 00，不能判断当前询问区间中是否存在 00。每次询问只能从 [l1,r1][l_1,r_1] 中选择数，所以需要使用前缀和统计 00 的数量，再通过区间前缀和之差判断当前区间中能否选择 00。
计算答案时不能直接把四种乘积全部取最大值。题目中小 Q 会在看到小 L 的选择后，让乘积尽量小。如果小 L 选择正数，小 Q 一定选择 BB 区间的最小值；如果小 L 选择负数，小 Q 一定选择 BB 区间的最大值；如果小 L 选择 00，乘积恒为 00。
确定小 Q 的选择后，再考虑小 L 应该选择哪一个数。当 BB 区间最小值非负时，选择最大正数；当它为负时，选择最小正数。当 BB 区间最大值非负时，选择最接近 00 的负数，也就是最大负数；当它为负时，选择绝对值最大的负数，也就是最小负数。

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

using ll = long long;

// 数组中的数最多为 1e9，乘积最多为 1e18。
// M 要比所有可能答案更大，用来表示“这一类数不存在”。
const ll M = 4000000000000000000LL;
const int N = 100000 + 10;

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

// zeroSum[i] 表示 a[1] 到 a[i] 中 0 的数量。
// 这样才能判断每次询问的区间中是否存在 0。
int zeroSum[N];

struct info_A {
    ll maxn;    // 区间最大值
    ll minn;    // 区间最小值
    ll minn_z;  // 区间内最小的正数，z 表示“正”
    ll maxn_f;  // 区间内最大的负数，f 表示“负”
} tree_A[N << 2];

struct info_B {
    ll maxn;    // 区间最大值
    ll minn;    // 区间最小值
} tree_B[N << 2];

/*
合并 A 的两个子区间。

为什么要维护这四个数？

当小 L 选择正数时，小 Q 会选择 B 区间最小值。
此时小 L 可能需要最大正数或最小正数。

当小 L 选择负数时，小 Q 会选择 B 区间最大值。
此时小 L 可能需要最大负数或最小负数。
*/
info_A operator+(info_A L, info_A R) {
    info_A rt;

    rt.maxn = max(L.maxn, R.maxn);
    rt.minn = min(L.minn, R.minn);

    /*
    minn_z 表示最小正数。

    如果一个子区间不存在正数，它的 minn_z 会被设为 M。
    M 比所有正常数据都大，取 min 时不会影响另一个区间的答案。
    */
    rt.minn_z = min(L.minn_z, R.minn_z);

    /*
    maxn_f 表示最大负数。

    如果一个子区间不存在负数，它的 maxn_f 会被设为 -M。
    -M 比所有正常数据都小，取 max 时不会影响另一个区间的答案。
    */
    rt.maxn_f = max(L.maxn_f, R.maxn_f);

    return rt;
}

void build_A(int l, int r, int rt) {
    if (l == r) {
        tree_A[rt].maxn = a[l];
        tree_A[rt].minn = a[l];

        /*
        minn_z 只能保存正数。

        如果 a[l] 是正数，它就是当前叶子中的最小正数；
        如果不是正数，就用 M 表示当前区间不存在正数。
        */
        if (a[l] > 0) {
            tree_A[rt].minn_z = a[l];
        } else {
            tree_A[rt].minn_z = M;
        }

        /*
        maxn_f 只能保存负数。

        如果 a[l] 是负数，它就是当前叶子中的最大负数；
        如果不是负数，就用 -M 表示当前区间不存在负数。
        */
        if (a[l] < 0) {
            tree_A[rt].maxn_f = a[l];
        } else {
            tree_A[rt].maxn_f = -M;
        }

        return;
    }

    int mid = (l + r) >> 1;

    build_A(l, mid, rt * 2);
    build_A(mid + 1, r, rt * 2 + 1);

    tree_A[rt] = tree_A[rt * 2] + tree_A[rt * 2 + 1];
}

info_A query_A(int l, int r, int rt, int L, int R) {
    if (l == L && r == R) {
        return tree_A[rt];
    }

    int mid = (l + r) >> 1;

    if (R <= mid) {
        return query_A(l, mid, rt * 2, L, R);
    } else if (L > mid) {
        return query_A(mid + 1, r, rt * 2 + 1, L, R);
    } else {
        return query_A(l, mid, rt * 2, L, mid)
             + query_A(mid + 1, r, rt * 2 + 1, mid + 1, R);
    }
}

info_B operator+(info_B L, info_B R) {
    info_B rt;

    // B 只需要查询区间最大值和区间最小值。
    rt.maxn = max(L.maxn, R.maxn);
    rt.minn = min(L.minn, R.minn);

    return rt;
}

void build_B(int l, int r, int rt) {
    if (l == r) {
        tree_B[rt] = {b[l], b[l]};
        return;
    }

    int mid = (l + r) >> 1;

    build_B(l, mid, rt * 2);
    build_B(mid + 1, r, rt * 2 + 1);

    tree_B[rt] = tree_B[rt * 2] + tree_B[rt * 2 + 1];
}

info_B query_B(int l, int r, int rt, int L, int R) {
    if (l == L && r == R) {
        return tree_B[rt];
    }

    int mid = (l + r) >> 1;

    if (R <= mid) {
        return query_B(l, mid, rt * 2, L, R);
    } else if (L > mid) {
        return query_B(mid + 1, r, rt * 2 + 1, L, R);
    } else {
        return query_B(l, mid, rt * 2, L, mid)
             + query_B(mid + 1, r, rt * 2 + 1, mid + 1, R);
    }
}

int main() {
    cin >> n >> m >> q;

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

        /*
        每次询问只能在 a[l_1] 到 a[r_1] 中选择数。
        整个数组中有 0，不代表当前询问区间中有 0，
        所以使用前缀和记录 0 的数量。
        */
        zeroSum[i] = zeroSum[i - 1] + (a[i] == 0);
    }

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

    build_A(1, n, 1);
    build_B(1, m, 1);

    while (q--) {
        int l_1, r_1, l_2, r_2;
        cin >> l_1 >> r_1 >> l_2 >> r_2;

        // 每棵线段树只查询一次，后面直接使用查询结果。
        info_A A = query_A(1, n, 1, l_1, r_1);
        info_B B = query_B(1, m, 1, l_2, r_2);

        ll maxn_ll = -M;

        /*
        第一类：小 L 选择正数 x。

        因为 x > 0，所以 x * y 随着 y 增大而增大。
        小 Q 想让乘积尽量小，因此一定会选择 B.minn。
        */
        if (A.maxn > 0) {
            if (B.minn >= 0) {
                /*
                B.minn 非负时，x 越大，x * B.minn 越大，
                所以小 L 应选择最大的正数 A.maxn。
                */
                maxn_ll = max(maxn_ll, A.maxn * B.minn);
            } else {
                /*
                B.minn 为负时，正数 x 越大，乘积反而越小。
                例如 2 * (-5) = -10，1 * (-5) = -5。
                所以小 L 应选择最小正数 A.minn_z。
                */
                maxn_ll = max(maxn_ll, A.minn_z * B.minn);
            }
        }

        /*
        第二类：小 L 选择负数 x。

        因为 x < 0，所以 x * y 随着 y 增大而减小。
        小 Q 想让乘积尽量小，因此一定会选择 B.maxn。
        */
        if (A.minn < 0) {
            if (B.maxn >= 0) {
                /*
                负数乘非负数时，小 L 应选择最接近 0 的负数。
                例如 (-1) * 5 = -5，比 (-2) * 5 = -10 更大。
                所以选择最大负数 A.maxn_f。
                */
                maxn_ll = max(maxn_ll, A.maxn_f * B.maxn);
            } else {
                /*
                B.maxn < 0，说明 B 区间中的数全为负数。
                负负得正，绝对值越大的负数得到的乘积越大，
                所以选择数值最小的负数 A.minn。
                */
                maxn_ll = max(maxn_ll, A.minn * B.maxn);
            }
        }

        /*
        第三类：小 L 选择 0。

        无论小 Q 选择什么数，乘积都是 0。
        只有当前 A 询问区间中确实存在 0 时，才能加入这个候选答案。
        */
        if (zeroSum[r_1] - zeroSum[l_1 - 1] > 0) {
            maxn_ll = max(maxn_ll, 0LL);
        }

        cout << maxn_ll << '\n';
    }
}
userId_undefined
去预览
0/2000
暂无数据

这里空空如也

热门讨论