[CSP-S 2022] 策略游戏 题解
Dregen_Yor · · 题解
更好的阅读体验。
题目链接。
思路
题目中重要条件：
小 L 的目标是使得这个得分尽可能大，小 Q 的目标是使得这个得分尽可能小。同时两人都是足够聪明的玩家，每次都会采用最优的策略。
也就是说，小 L 掌握主动权，小 L 选择后小 Q 才会从中选择一个数，使
我们模拟一下都会出现哪些情况。
-
小 L 和小 Q 都只能选择正整数，此时小 L 会选择最大的正整数，小 Q 会选择最小的正整数。
-
小 L 和小 Q 都只能选择负数，此时小 L 会选择最小的负数，小 Q 会选择最大的负数。
-
小 L 只能选择正整数，小 Q 既能选择正数又能选择负数，此时小 L 会选择最小的正整数，小 Q 会选择最小的负数。
-
小 L 只能选择负数，小 Q 既能选择正数又能选择负数，此时小 L 会选择最大的负数，小 Q 会选择最大的正整数。
-
小 L 既能选择正数又能选择负数，小 Q 只能选择正数，此时小 L 会选择最大的正数，小 Q 会选择最小的正数。
-
小 L 既能选择正数又能选择负数，小 Q 只能选择负数，此时小 L 会选择最小的负数，小 Q 会选择最大的负数。
-
小 L 既能选择正数又能选择负数，小 Q 也既能选择正数又能选择负数，此时答案会出现不同情况。当小 L 选择正整数时，小 Q 会选择最小的负数；当小 L 选择负数时，小 Q 会选择最大的正数。这种情况下，无论如何选择，结果一定是负数，我们要想让这个负数尽可能地大，那么小 L 在选择数的时候一定要选择绝对值相对较小的数，即小 L 应选择正数中的最小值或负数中的最大值，此时小 Q 选择的数分别为最小的负数与最大的正数，取两种情况的最大值即可。
通过上面的分析，我们发现前
我们在统计答案的时候只需要从两种极值的选择中取最小值最大的情况，然后判断是否存在第
至于两个序列的极值的查询，由于不涉及到修改操作，我们可以用 ST 表来维护两个序列的信息。
ST 表预处理复杂度为
代码
#include<bits/stdc++.h>
#define int long long
#include<cstdio>
using namespace std;
int n,m,q,a[100010],b[100010];
struct re{
__int128 a,b,c,d;
};
struct nod{
__int128 ST1[100010][20],ST2[100010][20],ST3[100010][20],ST4[100010][20];
void bulid(int *p,int len){
for(int i=1;i<=len;i++){
ST1[i][0]=p[i];
if(p[i]>=0){
ST2[i][0]=p[i];
}
else{
ST2[i][0]=2e9;
}
ST3[i][0]=p[i];
if(p[i]>0){
ST4[i][0]=-2e9;
}
else{
ST4[i][0]=p[i];
}
}
for(int j=1;j<=log2(len);j++){
for(int i=1;i<=len-(1<<j)+1;i++){
ST1[i][j]=min(ST1[i][j-1],ST1[i+(1<<(j-1))][j-1]);
ST2[i][j]=min(ST2[i][j-1],ST2[i+(1<<(j-1))][j-1]);
ST3[i][j]=max(ST3[i][j-1],ST3[i+(1<<(j-1))][j-1]);
ST4[i][j]=max(ST4[i][j-1],ST4[i+(1<<(j-1))][j-1]);
}
}
}
re query(int l,int r){
int len=r-l+1;
int p=log2(len);
int a=min(ST1[l][p],ST1[r-(1<<p)+1][p]);
int b=min(ST2[l][p],ST2[r-(1<<p)+1][p]);
int c=max(ST3[l][p],ST3[r-(1<<p)+1][p]);
int d=max(ST4[l][p],ST4[r-(1<<p)+1][p]);
return re{a,b,c,d};
}
}ST1,ST2;
signed main(){
// freopen("game.in","r",stdin);
// freopen("game.out","w",stdout);
scanf("%lld%lld%lld",&n,&m,&q);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
}
for(int i=1;i<=m;i++){
scanf("%lld",&b[i]);
}
ST1.bulid(a,n);
ST2.bulid(b,m);
while(q--){
int l1,r1,l2,r2;
scanf("%lld%lld%lld%lld",&l1,&r1,&l2,&r2);
re tmp1=ST1.query(l1,r1);
re tmp2=ST2.query(l2,r2);
int ans=max(min(tmp1.c*tmp2.a,tmp1.c*tmp2.c),min(tmp1.a*tmp2.c,tmp1.a*tmp2.a));
if(tmp1.b<1e9){
ans=max(ans,(int)tmp1.b*(int)tmp2.a);
}
if(tmp1.d>-1e9){
ans=max(ans,(int)tmp1.d*(int)tmp2.c);
}
printf("%lld\n",ans);
}
return 0;
}