P8818 [CSP-S 2022] 策略游戏

· · 个人记录

首先按照题意模拟：

int ans = -2e9;
for (int i = l1; i <= r1; i ++ )
{
    int t = 2e9;
    for (int j = l2; j <= r2; j ++ )
        t = min(t, a[i] * b[j]);
    ans = max(ans, t);
}

每次询问O(NM)，总的复杂度O(NMQ)。

考虑优化内层循环。

由于发现一直是取min操作，尝试维护最值。

目标是使t=min(a_ib_j)(l_2 \le j \le r_2)。

手推一下就会发现：

第2点必然正确，第1、3点证明类似，证明第1点：

设 b_1=min(b_j)，则 b_2 \ge b_1。

所以 $a_ib_1 \le a_ib_2$。 所以这样求出的$t$肯定是最小的。 询问区间最大值，最小值，可以用两个ST表或者线段树维护。如果用ST表可以做到 $O(1)$ 查询。 时间复杂度 $O(NQ)$。 --- 由于 $ans$ 也是取 $max(t)$，尝试对于 $a$ 数组进行最值维护。 $t$ 的取值范围必然在上述三种情况之中，分别设为$t_1,t_2,t_3$。 1. $a_i>0
  2. a_i < 0

注意 t_1,t_2,t_3 不一定存在，t_2 可以用前缀和维护是否有0出现。

注意情况1的a数组的最小值是大于0的，这是大前提；情况3的最大值也是小于0的。

这里我图个方便，打的是线段树，复杂度是O(Q(logN+logM))=O(Qlog(NM))。换成ST表可以做到O(Q+NlogN+MlogM)。两者都是O(NlogN)级别。

冗长的考场代码（记得开long long）：

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 100010;
const LL inf = 1e18 + 10;

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

int f[N][30], g[N][30];

void init(int w[], int n)
{
    for (int i = 1; i <= n; i ++ ) f[i][0] = g[i][0] = w[i];
    int t = log(n) / log(2) + 1;
    for (int j = 1; j <= t; j ++ )
        for (int i = 1; i + (1 << j) - 1 <= n; i ++ )
        {
            g[i][j] = min(g[i][j - 1], g[i + (1 << (j - 1))][j - 1]);
            f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
        }
}

int getmax(int l, int r)
{
    int t = log(r - l + 1) / log(2);
    return max(f[l][t], f[r - (1 << t) + 1][t]);
}

int getmin(int l, int r)
{
    int t = log(r - l + 1) / log(2);
    return min(g[l][t], g[r - (1 << t) + 1][t]);
}

struct Node
{
    int l, r;
    LL max, min, min0, max0;
}tr[N * 4];

void pushup(Node &root, Node &left, Node &right)
{
    root.max = max(left.max, right.max);
    root.min = min(left.min, right.min);
    root.min0 = min(left.min0, right.min0);
    root.max0 = max(left.max0, right.max0);
}

void pushup(int u)
{
    pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}

void build(int u, int l, int r)
{
    if (l == r) 
    {
        LL b = a[r] > 0 ? a[r] : inf;
        LL c = a[r] < 0 ? a[r] : -inf;
        tr[u] = {l, r, a[r], a[r], b, c};
    }
    else
    {
        tr[u] = {l, r};
        int mid = l + r >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

void init(Node &u)
{
    u.l = u.r = 0;
    u.max = u.max0 = -inf;
    u.min = u.min0 = inf;
}

Node query(int u, int l, int r)
{
    if (l <= tr[u].l && tr[u].r <= r) return tr[u];
    int mid = tr[u].l + tr[u].r >> 1;
    Node res, t1, t2;
    init(res), init(t1), init(t2);
    if (l <= mid) t1 = query(u << 1, l, r);
    if (r > mid) t2 = query(u << 1 | 1, l, r);
    pushup(res, t1, t2);
    return res;
}

int s0[N], s2[N];

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("%d", &a[i]);
    build(1, 1, n);

    for (int i = 1; i <= n; i ++ )
    {
        s0[i] = s0[i - 1];
        if (a[i] == 0) s0[i] ++ ;
    }

    for (int i = 1; i <= m; i ++ )
    {
        s2[i] = s2[i - 1];
        if (!b[i]) s2[i] ++;
    }

    for (int i = 1; i <= m; i ++ ) scanf("%d", &b[i]);
    init(b, m);
    while (q -- )
    {
        int l1, r1, l2, r2;
        scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
        LL res = -inf;
        LL y = getmin(l2, r2), z = getmax(l2, r2);
        Node u = query(1, l1, r1);
        if (u.max > 0)
        {
            res = max(res, u.max * y);
            res = max(res, u.min0 * y);
        }
        if (u.min < 0)
        {
            res = max(res, u.min * z);
            res = max(res, u.max0 * z);
        }
        if (s0[r1] - s0[l1 - 1])
        {
            res = max(res, 0ll);
        }
        printf("%lld\n", res);
    }
//  fclose(stdin);
//  fclose(stdout);
    return 0;
}