P8818 [CSP-S 2022] 策略游戏 题解
题目链接
简化题意
小 \(A\) 先在 \(a[l1,r1]\) 中选择一个数 \(x\)，小 \(B\) 再在 \(b[l2,r2]\) 中选择一个数 \(y\)，最后的分数就是 \(x \times y\)。
小 \(A\) 想让分数尽可能地大，而小 \(B\) 则想让分数尽可能地小，问最后的分数会是多少。
简要思路
分情况讨论：
-
当 \(x \ge 0\) 时，小 \(B\) 一定会选择一个最小的 \(y\);
-
当 \(x < 0\) 时，小 \(B\) 一定会选择一个最大的 \(y\)。
再来考虑小 \(A\) 的选择情况，同样是分类讨论：
-
当 \(x \ge 0\) 时，因为小 \(B\) 会选择最小的 \(y\)，所以：
-
当 \(y \ge 0\) 时，小 \(A\) 会让 \(x\) 更大，因为正数 \(\times\) 正数 \(=\) 正数；
-
当 \(y < 0\) 时，小 \(A\) 会让 \(x\) 更小，即选择最小的非负数（因为现在讨论的是 \(x \ge 0\) 的情况），因为负数 \(\times\) 正数 \(=\) 负数。
-
-
当 \(x < 0\) 时，因为小 \(B\) 会选择最大的 \(y\)，所以：
-
当 \(y \ge 0\) 时，小 \(A\) 会让 \(x\) 更大，即选择最大的负数（同理，因为现在讨论的是 \(x < 0\) 的情况），因为正数 \(\times\) 负数 \(=\) 负数；
-
当 \(y < 0\) 时，小 \(A\) 会让 \(x\) 更小，因为负数 \(\times\) 负数 \(=\) 正数。
-
综上所述，小 \(A\) 对数的选择只有四种：
-
选择区间内最大的数；
-
选择区间内最小的非负数；
-
选择区间内最大的负数；
-
选择区间内最小的数。
因此我们只需要分别讨论得到小 \(A\) 的这四种选择在小 \(B\) 经过选择后的最优解即可。
而因为我们也要考虑小 \(B\) 对答案的最优解，所以我们要维护六个区间最值，即六个 ST 表：
-
\(a\) 区间内的最大值；
-
\(a\) 区间内的最小值；
-
\(a\) 区间内的最小非负数（开始时将其赋值为一个极大值（因为维护时取最小值），从而方便判断该区间内是否有非负数）；
-
\(a\) 区间内的最大负数（同理，开始时赋为一个极小值（因为维护时取最大值），从而方便判断该区间内是否有负数）；
-
\(b\) 区间内的最大值；
-
\(b\) 区间内的最小值。
剩下部分就是 ST 表的板子了，这里放个 ST 表的讲解：
完整代码
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
const int MAXN=1e5+5;
const int MAX_log=25;
const int MAX=LONG_LONG_MAX;//极值
int n,m,q;
int l1,r1,l2,r2;
int lg[MAXN];//log(i)=lg[i] 即 2^(lg[i])<=i
int a[MAXN],b[MAXN];
//6 个 ST 表(第一维起点,第二维长度[2^j])
int a_max[MAXN][MAX_log];//a 区间最大值
int a_min[MAXN][MAX_log];//a 区间最小值
int b_max[MAXN][MAX_log];//b 区间最大值
int b_min[MAXN][MAX_log];//b 区间最小值
int af_max[MAXN][MAX_log];//a 负数区间最大值
int az_min[MAXN][MAX_log];//a 非负数区间最小值
signed main(){
std::cin>>n>>m>>q;
//---------ST 表的预处理---------
for(int i=1;i<=n;i++){
std::cin>>a[i];
a_max[i][0]=a_min[i][0]=a[i];
if(a[i]<0){
af_max[i][0]=a[i];
az_min[i][0]=MAX;//暂时没有非负数
}else{
af_max[i][0]=-MAX;//暂时没有负数
az_min[i][0]=a[i];
}
}
for(int i=1;i<=m;i++){
std::cin>>b[i];
b_max[i][0]=b_min[i][0]=b[i];
}
//---------lg 数组的预处理---------
for(int i=2;i<=std::max(n,m)+2;i++)
lg[i]=lg[i/2]+1;
//---------倍增思想（分开）的维护
for(int j=1;j<=lg[n];j++)//枚举区间长度
for(int i=1;i+(1<<j)-1<=n;i++){//枚举区间起点（注意先长度再起点）
int now=i+(1<<(j-1));//第一个区间终点-1、第二个区间起点
a_max[i][j]=std::max(a_max[i][j-1],a_max[now][j-1]);
af_max[i][j]=std::max(af_max[i][j-1],af_max[now][j-1]);
a_min[i][j]=std::min(a_min[i][j-1],a_min[now][j-1]);
az_min[i][j]=std::min(az_min[i][j-1],az_min[now][j-1]);
//以 i 为起点 长度为 2^j
//以 i 为起点 长度为 2^(j-1)
//以 i+2^(j-1) 为起点 长度为 2^(j-1)
}
for(int j=1;j<=lg[m];j++)//区间长度
for(int i=1;i+(1<<j)-1<=m;i++){//区间起点
int now=i+(1<<(j-1));
b_max[i][j]=std::max(b_max[i][j-1],b_max[now][j-1]);
b_min[i][j]=std::min(b_min[i][j-1],b_min[now][j-1]);//同上
}
//---------ST 表的查询---------
//两个 2的幂 覆盖整个序列 a a ab ab b b
while(q--){
std::cin>>l1>>r1>>l2>>r2;
int alg=lg[r1-l1+1],blg=lg[r2-l2+1];//a,b 序列的长度 2^alg 2^blg
int sta=r1-(1<<alg)+1,stb=r2-(1<<blg)+1;//后一个区间起点=终点-区间长度+1
int A_max=std::max(a_max[l1][alg],a_max[sta][alg]);
int Af_max=std::max(af_max[l1][alg],af_max[sta][alg]);
int A_min=std::min(a_min[l1][alg],a_min[sta][alg]);
int Az_min=std::min(az_min[l1][alg],az_min[sta][alg]);
//前一个区间（以 l1 开头 长度为 alg）
//后一个区间（以 sta 开头，长度为 alg）
int B_max=std::max(b_max[l2][blg],b_max[stb][blg]);
int B_min=std::min(b_min[l2][blg],b_min[stb][blg]);
//前一个区间（以 l2 开头 长度为 blg）
//后一个区间（以 stb 开头，长度为 blg）
int maxn=-MAX;
//分类讨论正负性，考虑小 B 的最优选择
maxn=std::max(maxn,A_max*(A_max>=0?B_min:B_max));
maxn=std::max(maxn,A_min*(A_min>=0?B_min:B_max));
if(Af_max!=-MAX)maxn=std::max(maxn,Af_max*(Af_max>=0?B_min:B_max));//有负数才更新
if(Az_min!=MAX)maxn=std::max(maxn,Az_min*(Az_min>=0?B_min:B_max));//有非负数才更新
std::cout<<maxn<<endl;
}
return 0;
}