P8818 [CSP-S 2022] 策略游戏

· · 题解

即给出 [l_1,r_1],[l_2,r_2] 分别从中选出两个数 x,y

则获得的价值为 A_x*B_y

小L：最大化 A_x*B_y

小Q：最小化 A_x*B_y

一：

设 [l_1,r_1] 中存在一个最大的 A_x 且 A_x\ge0，存在一个最小的数 A_x'\ge0，[l_2,r_2] 与上述情况一致，则最优策略为 max(A_x)*min(B_y)

二：

设 [l_1,r_1] 中存在一个最大的 A_x 且 A_x\ge0，存在一个最小的数 A_x'\ge0，[l_2,r_2] 中存在最大的 B_y\ge0，但最小的 B_y'<0，则此时的最优策略为 min(A_x)*min(B_y)

三：

设 [l_1,r_1] 中存在一个最大的 A_x 且 A_x\ge0，存在一个最小的数 A_x'<0，[l_2,r_2] 与上述情况一致，则最优策略为 max(min(A_x\ge0)*min(B_y),max(A_x<0)*max(B_y))

四：

设 [l_1,r_1] 中存在一个最大的 A_x 且 A_x\ge0，存在一个最小的数 A_x'<0，[l_2,r_2] 中存在最大的 B_y\ge0，且最小的 B_y'\ge0，则最优策略为 max(A_x)*min(B_y)

五：

设 [l_1,r_1] 中最大的数 A_x<0，[l_2,r_2] 中的数都大于或等于 0，则最优策略为 max(A_x)*max(B_y)

六：

设 [l_1,r_1] 中最大的数 A_x<0 ，[l_2,r_2] 中的数有 <0,\ge0，则最优策略为 max(A_x)*max(B_y)

七：

都小于0，则最优情况为 min(A_x)*max(B_y)

八：

if(MAX_A>=0&&MIN_A<0&&MAX_B<0)printf("%lld\n",MIN_A*MAX_B);

九：

if(MAX_A>=0&&MIN_A>=0&&MAX_B<0)printf("%lld\n",MIN_A*MIN_B);

#include<algorithm>
#include<iostream>
#include<string.h>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<map>
#include<set>
using namespace std;
#define int long long
#define repu(i,u) for(int i=(h[u]);i;i=(ne[i]))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
#define xx return
const int N=1e5+10;

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

struct Tree{
    int max_n,min_n;
    int max_z,min_z;
    #define min_n(p,id) t[p][id].min_n
    #define max_n(p,id) t[p][id].max_n
    #define min_z(p,id) t[p][id].min_z
    #define max_z(p,id) t[p][id].max_z
}t[N*4][2];

void build(int p,int l,int r,int id)
{
    if(l==r)
    {
        if(id==0)
        {
            max_n(p,id)=a[l];
            min_n(p,id)=a[l];
            if(a[l]>=0)max_z(p,id)=a[l],min_z(p,id)=-2e18;
            else min_z(p,id)=a[l],max_z(p,id)=2e18;
        }
        else{
            max_n(p,id)=b[l];
            min_n(p,id)=b[l];
            if(b[l]>=0)max_z(p,id)=b[l],min_z(p,id)=-2e18;
            else min_z(p,id)=b[l],max_z(p,id)=2e18;
        }
        xx;
    }
    int mid=l+r>>1;
    build(p*2,l,mid,id),build(p*2+1,mid+1,r,id);
    max_n(p,id)=max(max_n(p*2,id),max_n(p*2+1,id));
    min_n(p,id)=min(min_n(p*2,id),min_n(p*2+1,id));
    max_z(p,id)=min(max_z(p*2,id),max_z(p*2+1,id));
    min_z(p,id)=max(min_z(p*2,id),min_z(p*2+1,id));
}

int ask_max_n(int p,int l,int r,int L,int R,int id)
{
    if(L<=l&&r<=R)xx max_n(p,id);
    int mid=l+r>>1;
    int ans=-2e18;
    if(L<=mid)ans=max(ans,ask_max_n(p*2,l,mid,L,R,id));
    if(R>mid)ans=max(ans,ask_max_n(p*2+1,mid+1,r,L,R,id));
    xx ans;
}

int ask_min_n(int p,int l,int r,int L,int R,int id)
{
    if(L<=l&&r<=R)xx min_n(p,id);
    int mid=l+r>>1;
    int ans=2e18;
    if(L<=mid)ans=min(ans,ask_min_n(p*2,l,mid,L,R,id));
    if(R>mid)ans=min(ans,ask_min_n(p*2+1,mid+1,r,L,R,id));
    xx ans;
}

int ask_max_z(int p,int l,int r,int L,int R,int id)
{
    if(L<=l&&r<=R)xx max_z(p,id);
    int mid=l+r>>1;
    int ans=2e18;
    if(L<=mid)ans=min(ans,ask_max_z(p*2,l,mid,L,R,id));
    if(R>mid)ans=min(ans,ask_max_z(p*2+1,mid+1,r,L,R,id));
    xx ans;
}

int ask_min_z(int p,int l,int r,int L,int R,int id)
{
    if(L<=l&&r<=R)xx min_z(p,id);
    int mid=l+r>>1;
    int ans=-2e18;
    if(L<=mid)ans=max(ans,ask_min_z(p*2,l,mid,L,R,id));
    if(R>mid)ans=max(ans,ask_min_z(p*2+1,mid+1,r,L,R,id));
    xx ans;
}

void solve()
{
    scanf("%lld%lld%lld",&n,&m,&q);
    rep(i,1,n)scanf("%lld",&a[i]);
    rep(i,1,m)scanf("%lld",&b[i]);
    build(1,1,n,0);build(1,1,m,1);
    rep(i,1,q)
    {
        int l1,r1,l2,r2;scanf("%lld%lld%lld%lld",&l1,&r1,&l2,&r2);
        int MAX_A=ask_max_n(1,1,n,l1,r1,0);
        int MAX_B=ask_max_n(1,1,m,l2,r2,1);
        int MIN_A=ask_min_n(1,1,n,l1,r1,0);
        int MIN_B=ask_min_n(1,1,m,l2,r2,1);
        if(MAX_A>=0&&MIN_A>=0&&MAX_B>=0&&MIN_B>=0)//1
        {
            printf("%lld\n",(MAX_A*MIN_B));
        }
        if(MAX_A>=0&&MIN_A>=0&&MAX_B>=0&&MIN_B<0)//2
        {
            printf("%lld\n",(MIN_A*MIN_B));
        }
        if(MAX_A>=0&&MIN_A<0&&MAX_B>=0&&MIN_B<0)//3
        {
            int MAX_A_Z=ask_max_z(1,1,n,l1,r1,0);
            int MIN_A_Z=ask_min_z(1,1,n,l1,r1,0);
            int ans=-2e18;
            if(MAX_A_Z!=2e18)
            {
                ans=MAX_A_Z*MIN_B;
            }
            if(MIN_A_Z!=-2e18)
            {
                ans=max(ans,MIN_A_Z*MAX_B);
            }
            printf("%lld\n",ans);
        }
        if(MAX_A>=0&&MIN_A<0&&MAX_B>=0&&MIN_B>=0)//4
        {
            printf("%lld\n",MAX_A*MIN_B);
        }
        if(MAX_A>=0&&MIN_A<0&&MAX_B<0)//8
        {
            printf("%lld\n",MIN_A*MAX_B);
        }
        if(MAX_A>=0&&MIN_A>=0&&MAX_B<0)//9
        {
            printf("%lld\n",MIN_A*MIN_B);
        }
        if(MAX_A<0&&MAX_B>=0&&MIN_B>=0)//5
        {
            printf("%lld\n",MAX_A*MAX_B);
        }
        if(MAX_A<0&&MAX_B>=0&&MIN_B<0)//6
        {
            printf("%lld\n",MAX_A*MAX_B);
        }
        if(MAX_A<0&&MAX_B<0)//7
        {
            printf("%lld\n",MIN_A*MAX_B);
        }
    }
    xx;
}

signed main()
{
    solve();xx 0;
}