95pts求助
查看原帖
95pts求助
359492
BZHZS楼主2022/11/5 15:13

线段树最后一个点wa了,头发快掉光了。

#include <bits/stdc++.h>
#define ll long long
#define BZHZS puts("BZH is a handsome boy.");
using namespace std;

const int N = 100010;

struct node
{
    ll zmaxx, zminn, fmaxx, fminn;
};

int n, m, q, xa, ya, xb, yb;
ll a[N], b[N], a0[N], b0[N], ans, roc;
node at[4 * N], bt[4 * N], sa, sb;

inline ll read()
{
    ll f = 1, s = 0;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
    {
        s = (s << 1) + (s << 3) + c - '0';
        c = getchar();
    }
    return s * f;
}

void builda(int x, int l, int r)
{
    if (l == r)
    {
        if (a[l] > 0)
        {
            at[x] = node{a[l], a[l], INT_MIN, 0};
            // printf("%lld %lld %lld %lld\n", at[x].zmaxx, at[x].zminn, at[x].fmaxx, at[x].fminn);
        }
        else if (a[l] < 0)
        {
            at[x] = node{0, INT_MAX, a[l], a[l]};
            // printf("%lld %lld %lld %lld\n", at[x].zmaxx, at[x].zminn, at[x].fmaxx, at[x].fminn);
        }
        else
        {
            at[x] = node{0, INT_MAX, INT_MIN, 0};
        }
        return;
    }
    int mid = (l + r) / 2;
    builda(x * 2, l, mid);
    builda(x * 2 + 1, mid + 1, r);
    at[x].fmaxx = max(at[x * 2].fmaxx, at[x * 2 + 1].fmaxx);
    at[x].fminn = min(at[x * 2].fminn, at[x * 2 + 1].fminn);
    at[x].zmaxx = max(at[x * 2].zmaxx, at[x * 2 + 1].zmaxx);
    at[x].zminn = min(at[x * 2].zminn, at[x * 2 + 1].zminn);
    // printf("%lld %lld %lld %lld\n", at[x].zmaxx, at[x].zminn, at[x].fmaxx, at[x].fminn);
}

void buildb(int x, int l, int r)
{
    if (l == r)
    {
        if (b[l] > 0)
        {
            bt[x] = node{b[l], b[l], INT_MIN, 0};
        }
        else if (b[l] < 0)
        {
            bt[x] = node{0, INT_MAX, b[l], b[l]};
        }
        else
        {
            bt[x] = node{0, INT_MAX, INT_MIN, 0};
        }
        return;
    }
    int mid = (l + r) / 2;
    buildb(x * 2, l, mid);
    buildb(x * 2 + 1, mid + 1, r);
    bt[x].fmaxx = max(bt[x * 2].fmaxx, bt[x * 2 + 1].fmaxx);
    bt[x].fminn = min(bt[x * 2].fminn, bt[x * 2 + 1].fminn);
    bt[x].zmaxx = max(bt[x * 2].zmaxx, bt[x * 2 + 1].zmaxx);
    bt[x].zminn = min(bt[x * 2].zminn, bt[x * 2 + 1].zminn);
}

node finda(int x, int L, int R, int l, int r)
{
    if (l <= L && R <= r)
    {
        return at[x];
    }
    int mid = (L + R) / 2;
    node res = node{0, INT_MAX, INT_MIN, 0}, tl = node{0, INT_MAX, INT_MIN, 0}, tr = node{0, INT_MAX, INT_MIN, 0};
    if (l <= mid)
        tl = finda(x * 2, L, mid, l, r);
    if (mid < r)
        tr = finda(x * 2 + 1, mid + 1, R, l, r);
    res.fmaxx = max(tl.fmaxx, tr.fmaxx);
    res.fminn = min(tl.fminn, tr.fminn);
    res.zmaxx = max(tl.zmaxx, tr.zmaxx);
    res.zminn = min(tl.zminn, tr.zminn);
    return res;
}

node findb(int x, int L, int R, int l, int r)
{
    if (l <= L && R <= r)
    {
        return bt[x];
    }
    int mid = (L + R) / 2;
    node res = node{0, INT_MAX, INT_MIN, 0}, tl = node{0, INT_MAX, INT_MIN, 0}, tr = node{0, INT_MAX, INT_MIN, 0};
    if (l <= mid)
        tl = findb(x * 2, L, mid, l, r);
    if (mid < r)
        tr = findb(x * 2 + 1, mid + 1, R, l, r);
    res.fmaxx = max(tl.fmaxx, tr.fmaxx);
    res.fminn = min(tl.fminn, tr.fminn);
    res.zmaxx = max(tl.zmaxx, tr.zmaxx);
    res.zminn = min(tl.zminn, tr.zminn);
    return res;
}

int main()
{
    // ios::sync_with_stdio(0);
    // cin.tie(0), cout.tie(0);
    // freopen("BZHZS.in", "r", stdin);
    // freopen("BZHZS.out", "w", stdout);

    n = read(), m = read(), q = read();
    for (int i = 1; i <= n; i++)
        a[i] = read(), a0[i] = a0[i - 1] + (a[i] == 0);
    for (int i = 1; i <= m; i++)
        b[i] = read(), b0[i] = b0[i - 1] + (b[i] == 0);

    builda(1, 1, n);
    buildb(1, 1, m);

    for (int i = 1; i <= q; i++)
    {
        roc = LONG_LONG_MIN;
        xa = read(), ya = read(), xb = read(), yb = read();
        sa = finda(1, 1, n, xa, ya);
        sb = findb(1, 1, m, xb, yb);
        // printf("%lld %lld %lld %lld :: %lld %lld %lld %lld\n", sa.zmaxx, sa.zminn, sa.fmaxx, sa.fminn, sb.zmaxx, sb.zminn, sb.fmaxx, sb.fminn);
        if (sa.zmaxx != 0)
        {
            if (sb.fminn != 0)
            {
                roc = max(roc, sa.zmaxx * sb.fminn);
            }
            else
            {
                roc = max(roc, sa.zmaxx * sb.zminn);
            }
        }
        if (sa.zminn != INT_MAX)
        {
            if (sb.fminn != 0)
            {
                roc = max(roc, sa.zminn * sb.fminn);
            }
            else
            {
                roc = max(roc, sa.zminn * sb.zminn);
            }
        }
        if (sa.fmaxx != INT_MIN)
        {
            if (sb.zmaxx != 0)
            {
                roc = max(roc, sa.fmaxx * sb.zmaxx);
            }
            else
            {
                roc = max(roc, sa.fmaxx * sb.fmaxx);
            }
        }
        if (sa.fminn != 0)
        {
            if (sb.zmaxx != 0)
            {
                roc = max(roc, sa.fminn * sb.zmaxx);
            }
            else
            {
                roc = max(roc, sa.fminn * sb.fmaxx);
            }
        }
        if (roc < 0 && a0[ya] - a0[xa] > 0)
        {
            puts("0");
        }
        else if (roc > 0 && b0[yb] - b0[xb] > 0)
        {
            puts("0");
        }
        else
        {
            printf("%lld\n", roc);
        }
    }

    return 0;
}

2022/11/5 15:13
加载中...