题解 P8818【[CSP-S 2022] 策略游戏】

· · 题解

problem

长度为 n 的数组 a，长度为 m 的数组 b。q 次博弈，每次博弈给出 [l_1,r_1],[l_2,r_2]，Alice 可以选择一个 i\in[l_1,r_1]，Bob 在看到 Alice 的选择后可以选择一个 j\in[l_2,r_2]，最终游戏的得分为 a_ib_j。Alice 希望得分尽可能大，Bob 希望得分尽可能小，在他们都绝顶聪明的情况下，每次游戏的得分各是多少？

solution

我会暴力！枚举 Alice 和 Bob 选的数，那么答案是这个东西：

[*]=\max_i\{\min_j a_ib_j\}.

考虑优化它。假如我们有 0<x<y<z，如果 y 是一种决策，那么显然 x,z 其中之一会优于 y，那么 y 就没用了。负数也是一样的。综上，真正有用的决策只有 \min,\max_{x<0}x,0,\min_{x>0}x,\max，其它一定不会成为最优决策。

这五个值显然可以 RMQ，而枚举部分的复杂度也降为常数，于是直接暴力就可以了。

code

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
int lg[100010];
template<int N,int D=1,class T=LL> struct STable{
    T f[21][N+10]; int cnt;
    STable():cnt(0){}
    void insert(T x){
        f[0][++cnt]=x*D;
        for(int j=1;1<<j<=cnt;j++){
            int i=cnt-(1<<j)+1;
            f[j][i]=min(f[j-1][i],f[j-1][i+(1<<(j-1))]);
        }
    }
    T query(int l,int r){
        int k=lg[r-l+1];
        return min(f[k][l],f[k][r-(1<<k)+1])*D;
    }
};
int n,m,q,sa[100010],sb[100010];
LL a[100010],b[100010];
STable<100010,1> tmin[4];
STable<100010,-1> tmax[4];
int main(){
    //freopen("game.in","r",stdin),freopen("game.out","w",stdout);
    lg[0]=-1; for(int i=1;i<=1e5;i++) lg[i]=lg[i>>1]+1;
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        sa[i]=sa[i-1]+!a[i];
        tmin[0].insert(a[i]<0?a[i]:1e18);
        tmin[1].insert(a[i]>0?a[i]:1e18);
        tmax[0].insert(a[i]<0?a[i]:-1e18);
        tmax[1].insert(a[i]>0?a[i]:-1e18);
    }
    for(int i=1;i<=m;i++){
        scanf("%lld",&b[i]);
        sb[i]=sb[i-1]+!b[i];
        tmin[2].insert(b[i]<0?b[i]:1e18);
        tmin[3].insert(b[i]>0?b[i]:1e18);
        tmax[2].insert(b[i]<0?b[i]:-1e18);
        tmax[3].insert(b[i]>0?b[i]:-1e18);
    }
    for(int l,r;q--;){
        scanf("%d%d",&l,&r);
        LL pa[]={tmin[0].query(l,r),tmax[0].query(l,r),sa[r]-sa[l-1]?0:(LL)1e18,tmin[1].query(l,r),tmax[1].query(l,r)};
        scanf("%d%d",&l,&r);
        LL pb[]={tmin[2].query(l,r),tmax[2].query(l,r),sb[r]-sb[l-1]?0:(LL)1e18,tmin[3].query(l,r),tmax[3].query(l,r)};
        LL ans=-1e18;
        for(int i=0;i<5;i++){
            if(pa[i]==1e18||pa[i]==-1e18) continue;
            LL res=1e18;
            for(int j=0;j<5;j++){
                if(pb[j]==1e18||pb[j]==-1e18) continue;
                res=min(res,pa[i]*pb[j]);
            }
            ans=max(ans,res);
        }
        printf("%lld\n",ans);
    }
    return 0;
}