【题解】P8818 [CSP-S 2022] 策略游戏
这道题应该是 CSP-S2022 所有题里面最简单的一道了，主要是有点套路，刨开套路，其实就是个静态维护区间最大最小值的板子。
作为一名场外 VP 选手，写一篇题解来记录一下这道题的解题过程。
题目链接
题意概述
这里只写一下转化后的题意吧。
给定一个长度为 \(n\) 的数组 \(A\) 和一个长度为 \(m\) 的数组 \(B\)。
要进行 \(q\) 轮选数。每轮会给定 \(l_1,r_1,l_2,r_2\)。甲会先在数组 \(A\) 的区间 \([l_1,r_1]\) 内选择一个数 \(x\)，然后乙会在数组 \(B\) 的区间 \([l_2,r_2]\) 内选择一个数 \(y\)，这一轮的得分记为 \(a_x \times b_y\)。甲想让得分尽可能大，乙想让得分尽可能小，两个人都采用最优策略，问每轮选数的得分是多少。
思路分析
首先遇到最优策略问题，一个常见的套路是：先从后手的角度思考问题。
我们考虑当甲选的数确定时，乙会选择什么。
首先显然的一点是，假设甲选择的是 \(x\)，那么乙一定选择的是区间 \([l_2,r_2]\) 内使得 \(a_x\times b_y\) 最小的 \(y\)。那么我们来分类讨论一下：
-
当 \(a_x \ge 0\) 时，乙选择的是区间 \([l_2,r_2]\) 内最小的 \(a_y\)。
因为很显然，乙是为了让得分尽可能小，那么当区间 \([l_2,r_2]\) 里有负数时，他一定会选择最小的负数；没有负数时，他一定会选择最小的非负数。所以无论如何他都会选择最小的数。
-
当 \(a_x <0\) 时，乙选择的是区间 \([l_2,r_2]\) 内最大的 \(a_y\)。
同理，当有非负数时，他一定会选择最大的非负数；无非负数，他一定会选择最大的负数来使得得分尽可能小。所以不管怎么样他都会选择区间内最大的数。
乙的选择我们已经确定了，现在来看甲的选择。
我们一样采用分类讨论的办法：
- 当甲选择的 \(a_x \ge 0\) 时，那乙选择最小的 \(a_y\)。
- 若 \(a_y < 0\)，那么结果一定是个非正数，所以甲要选择最小的非负数使得得分的绝对值尽可能小，从而结果尽可能大；
- 若 \(a_y \ge 0\)，那么结果一定是个非负数，所以甲要选择最大的非负数使得得分的绝对值尽可能大，从而结果也尽可能大。
- 当甲选择的 \(a_x<0\) 时，那乙选择最大的 \(a_y\)。
- 若 \(a_y<0\)，那么结果一定是个正数，所以甲要选择最小的负数使得得分的绝对值尽可能大，从而结果也尽可能大；
- 若 \(a_y>0\)，那么结果一定是个负数，所以甲要选择最大的负数使得得分的绝对值尽可能小，从而结果尽可能大。
综上所述，可知甲的选择只有可能是区间内最大的非负数，最小的非负数，以及最大的负数和最小的负数。然后乙的选择只可能是区间最大/最小值。
所以我们只需要建立一个数据结构，用来维护静态区间最大最小值。
可以用 ST 表/线段树来解决。
如果选择 ST 表，则可以维护六个 ST 表，分别维护：数组 \(A\) 的非负数区间最大值，数组 \(A\) 的非负数区间最小值，数组 \(A\) 的负数区间最大值，数组 \(A\) 的区间最小值，数组 \(B\) 的区间最大值，数组 \(B\) 的区间最小值。
如果选择线段树，则可以建立三棵线段树，分别维护：数组 \(A\) 的非负数，数组 \(A\) 的负数，以及数组 \(B\) 内所有元素，然后每次查询每棵线段树内的区间最大和最小值。
不管是 ST 表还是线段树，我们都只需要考虑甲的每次选择下乙的选择，并将每种情况下他们俩的选择相乘最后取最大值即可。
实现代码
线段树做法
//B
#include<iostream>
#include<cstdio>
#include<algorithm>
//#define debug
#define mid ((l+r)>>1)
#define ls (now<<1)
#define rs ((now<<1)|1)
#define int long long
using namespace std;
const int maxn=1e5+10;
const int INF=1e18+1;
int a[maxn],b[maxn];
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*f;
}
struct Seg{//注意可以采用结构体的方式更为简便。
int mx[maxn<<2],mi[maxn<<2];
void pu(int now)
{
mx[now]=max(mx[ls],mx[rs]);
mi[now]=min(mi[ls],mi[rs]);
}
void ins(int now,int l,int r,int pos,int v,int opt)
{
if(l==r)
{
if(opt)mx[now]=-INF,mi[now]=INF;//注意这里的处理方式。对于数组 A 的非负数，那么将它插入到负数的线段树内时，只需要将它所在位置的值的 mx 设为极小值，mi 设为极大值即可。对于数组 A 的负数也同理。
else mx[now]=mi[now]=v;
return ;
}
if(pos<=mid)ins(ls,l,mid,pos,v,opt);
else ins(rs,mid+1,r,pos,v,opt);
pu(now);
}
int qmax(int now,int l,int r,int L,int R)
{
if(L<=l&&r<=R){return mx[now];}
int ret=-INF;
if(L<=mid)ret=qmax(ls,l,mid,L,R);
if(R>mid)ret=max(ret,qmax(rs,mid+1,r,L,R));
return ret;
}
int qmin(int now,int l,int r,int L,int R)
{
if(L<=l&&r<=R){return mi[now];}
int ret=INF;
if(L<=mid)ret=qmin(ls,l,mid,L,R);
if(R>mid)ret=min(ret,qmin(rs,mid+1,r,L,R));
return ret;
}
}tra[2],trb;
signed main()
{
// freopen("game.in","r",stdin);
// freopen("game.out","w",stdout);
int n,m,q;
n=read();m=read();q=read();
for(int i=1;i<=n;i++)
{
a[i]=read();
if(a[i]>=0)
{
tra[0].ins(1,1,n,i,a[i],0);
tra[1].ins(1,1,n,i,a[i],1);
}
else
{
tra[1].ins(1,1,n,i,a[i],0);
tra[0].ins(1,1,n,i,a[i],1);
}
}
for(int i=1;i<=m;i++)
{
b[i]=read();
trb.ins(1,1,n,i,b[i],0);
}
while(q--)
{
int l1,r1,l2,r2;
l1=read();r1=read();l2=read();r2=read();
int maxz=tra[0].qmax(1,1,n,l1,r1);
int minz=tra[0].qmin(1,1,n,l1,r1);
int maxf=tra[1].qmax(1,1,n,l1,r1);
int minf=tra[1].qmin(1,1,n,l1,r1);
int maxb=trb.qmax(1,1,n,l2,r2);
int minb=trb.qmin(1,1,n,l2,r2);
int ans1,ans2,ans3,ans4;
if(maxz>=0)ans1=maxz*minb;
else ans1=-INF;
if(minz<INF)ans2=minz*minb;
else ans2=-INF;
if(maxf>-INF)ans3=maxf*maxb;
else ans3=-INF;
if(minf<0)ans4=minf*maxb;
else ans4=-INF;
cout<<max({ans1,ans2,ans3,ans4})<<'\n';
}
return 0;
}
ST 表解法
//luoguP8818
//ST 表做法
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define int long long
using namespace std;
const int maxn=1e5+10;
const int INF=2e18;
int mxaz[maxn][25],miaz[maxn][25],mxaf[maxn][25],miaf[maxn][25],mxb[maxn][25],mib[maxn][25];
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*f;
}
signed main()
{
int n,m,q;
n=read();m=read();q=read();
for(int i=1;i<=n;i++)
{
int x=read();
if(x>=0)
{
miaz[i][0]=mxaz[i][0]=x;
miaf[i][0]=INF;
mxaf[i][0]=-INF;//这里的处理方式同线段树中 opt。
}
else
{
miaf[i][0]=mxaf[i][0]=x;
miaz[i][0]=INF;
mxaz[i][0]=-INF;
}
}
for(int i=1;i<=m;i++)
{
int x=read();
mxb[i][0]=mib[i][0]=x;
}
for(int j=1;j<=log2(n);j++)
{
for(int i=1;i+(1<<j)-1<=n;i++)
{
mxaz[i][j]=max(mxaz[i][j-1],mxaz[i+(1<<(j-1))][j-1]);
mxaf[i][j]=max(mxaf[i][j-1],mxaf[i+(1<<(j-1))][j-1]);
miaz[i][j]=min(miaz[i][j-1],miaz[i+(1<<(j-1))][j-1]);
miaf[i][j]=min(miaf[i][j-1],miaf[i+(1<<(j-1))][j-1]);
}
}
for(int j=1;j<=log2(m);j++)
{
for(int i=1;i+(1<<j)-1<=m;i++)
{
mxb[i][j]=max(mxb[i][j-1],mxb[i+(1<<(j-1))][j-1]);
mib[i][j]=min(mib[i][j-1],mib[i+(1<<(j-1))][j-1]);
}
}
while(q--)
{
int l1,l2,r1,r2;
l1=read();r1=read();l2=read();r2=read();
int sta1=log2(r1-l1+1);
int sta2=log2(r2-l2+1);
int maxz=max(mxaz[l1][sta1],mxaz[r1-(1<<sta1)+1][sta1]);
int minz=min(miaz[l1][sta1],miaz[r1-(1<<sta1)+1][sta1]);
int maxf=max(mxaf[l1][sta1],mxaf[r1-(1<<sta1)+1][sta1]);
int minf=min(miaf[l1][sta1],miaf[r1-(1<<sta1)+1][sta1]);
int maxb=max(mxb[l2][sta2],mxb[r2-(1<<sta2)+1][sta2]);
int minb=min(mib[l2][sta2],mib[r2-(1<<sta2)+1][sta2]);
int ans1,ans2,ans3,ans4;
if(maxz>=0)ans1=maxz*minb;
else ans1=-INF;
if(minz<INF)ans2=minz*minb;
else ans2=-INF;
if(maxf>-INF)ans3=maxf*maxb;
else ans3=-INF;
if(minf<0)ans4=minf*maxb;
else ans4=-INF;
cout<<max({ans1,ans2,ans3,ans4})<<'\n';
}
}