P8818 [CSP-S 2022] 策略游戏
以下的分析,定义正数 \(\ge 0\),负数 \(\le 0\)。
我们发现,如果第一个人取了正数,第二个人如果有负数,那么就取绝对值最大的负数,即最小的数;如果没有,就取最小的正数,也是最小的数。
如果第一个人取了负数,第二个人如果有正数,那么就取最大的正数,即最大的数;如果没有,就取绝对值最小的负数,也是最大的数。
于是,第二个人的最优策略只有最大值或者最小值。
对于第一个人,我们发现他只可能取最小的正数、最大的负数、最小值、最大值四者其一。
所以我们只要枚举第一个人的四选一,第二人的二选一,然后判断一下第一个人是否存在最小的正数、最大的负数即可。
第一个人要 \(4\) 个最值,第二个人 \(2\) 个,于是开了 \(6\) 个 ST
表维护。
时间复杂度 \(O(n\log n+m\log m+q)\)。
#include<cstdio>
#include<algorithm>
using namespace std;
#define Ed for(int i=h[x];~i;i=ne[i])
#define Ls(i,l,r) for(int i=l;i<r;++i)
#define Rs(i,l,r) for(int i=l;i>r;--i)
#define Le(i,l,r) for(int i=l;i<=r;++i)
#define Re(i,l,r) for(int i=l;i>=r;--i)
#define L(i,l) for(int i=0;i<l;++i)
#define E(i,l) for(int i=1;i<=l;++i)
#define W(t) while(t--)
#define Wh while
typedef long long ll;
const int N=100010,M=17,INF=1e9+1;
int n,m,q,a[N],b[N],LOG[N],amx[M][N],amn[M][N],bmx[M][N],bmn[M][N],fmx[M][N],zmn[M][N];
void init(int mn[][N],int mx[][N],int n,int a[]){
E(i, n)mn[0][i]=mx[0][i]=a[i];
E(i, LOG[n])
for(int j=1;j+(1<<i)-1<=n;++j){
mn[i][j]=min(mn[i-1][j],mn[i-1][j+(1<<i-1)]);
mx[i][j]=max(mx[i-1][j],mx[i-1][j+(1<<i-1)]);
}
}
void Init(){
E(i, n){
fmx[0][i]=a[i]<=0?a[i]:-INF;
zmn[0][i]=a[i]>=0?a[i]:INF;
}
E(i, LOG[n])
for(int j=1;j+(1<<i)-1<=n;++j){
zmn[i][j]=min(zmn[i-1][j],zmn[i-1][j+(1<<i-1)]);
fmx[i][j]=max(fmx[i-1][j],fmx[i-1][j+(1<<i-1)]);
}
}
int qmax(int f[][N],int l,int r){
int k=LOG[r-l+1];
return max(f[k][l],f[k][r-(1<<k)+1]);
}
int qf(int l,int r){
int k=LOG[r-l+1];
return max(fmx[k][l],fmx[k][r-(1<<k)+1]);
}
int qz(int l,int r){
int k=LOG[r-l+1];
return min(zmn[k][l],zmn[k][r-(1<<k)+1]);
}
int qmin(int f[][N],int l,int r){
int k=LOG[r-l+1];
return min(f[k][l],f[k][r-(1<<k)+1]);
}
int main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
#endif
scanf("%d%d%d",&n,&m,&q);
int lim=max(n,m);
Le(i, 2, lim)LOG[i]=LOG[i>>1]+1;
E(i, n)scanf("%d",a+i);
E(i, m)scanf("%d",b+i);
init(amn,amx,n,a);
init(bmn,bmx,m,b);
Init();
W(q){
int l1,r1,l2,r2;
scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
ll aa[]={qz(l1,r1),qf(l1,r1),qmax(amx,l1,r1),qmin(amn,l1,r1)};
ll bb[]={qmax(bmx,l2,r2),qmin(bmn,l2,r2)};
ll ans=-2e18;
L(i, 4)
if(i>1||aa[i]!=INF&&aa[i]!=-INF)
ans=max(ans,min(aa[i]*bb[0],aa[i]*bb[1]));
printf("%lld\n",ans);
}
return 0;
}
标签:aa,r1,int,策略,负数,l1,正数,游戏
From: https://www.cnblogs.com/wscqwq/p/17729845.html