P8818 [CSP-S 2022] 策略游戏

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int qwe=1e5+4,MAX=LONG_LONG_MAX,MIN=LONG_LONG_MIN;
int n,m,q,a[qwe],b[qwe],lg[25];
int amax[qwe][25],amin[qwe][25],azin[qwe][25],afax[qwe][25];
int bmax[qwe][25],bmin[qwe][25];
/*
azin:a的非负数区间最小值
afax:a的负数区间最大值
*/
signed main(){
//	freopen("game4.in","r",stdin);
//	freopen("1.txt","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]);
	for(int i=2;i<=max(n,m);++i)lg[i]=lg[i>>1]+1;
	
	for(int i=1;i<=n;++i){
		amax[i][0]=amin[i][0]=a[i];
		azin[i][0]=(a[i]>=0?a[i]:MAX);
		afax[i][0]=(a[i]<0?a[i]:MIN);
	}
	for(int j=1;j<=lg[n];++j)
		for(int i=1;i+(1<<j)<=n+1;++i){
			int p=i+(1<<(j-1));
			amax[i][j]=max(amax[i][j-1],amax[p][j-1]);
			amin[i][j]=min(amin[i][j-1],amin[p][j-1]);
			afax[i][j]=max(afax[i][j-1],afax[p][j-1]);
			azin[i][j]=min(azin[i][j-1],azin[p][j-1]);
		}
		
	for(int i=1;i<=m;++i)bmax[i][0]=bmin[i][0]=b[i];
	for(int j=1;j<=lg[m];++j)
		for(int i=1;i+(1<<j)<=m+1;++i){
			int p=i+(1<<(j-1));
			bmax[i][j]=max(bmax[i][j-1],bmax[p][j-1]);
			bmin[i][j]=min(bmin[i][j-1],bmin[p][j-1]);
		}
	
	int la,lb,ra,rb;
	while(q--){
		cin>>la>>ra>>lb>>rb;
		int ta=lg[ra-la+1],tb=lg[rb-lb+1];
		int pa=ra-(1<<ta)+1,pb=rb-(1<<tb)+1;
		
		int amaxx=max(amax[la][ta],amax[pa][ta]);
		int aminn=min(amin[la][ta],amin[pa][ta]);
		int afaxx=max(afax[la][ta],afax[pa][ta]);
		int azinn=min(azin[la][ta],azin[pa][ta]);
		int bmaxx=max(bmax[lb][tb],bmax[pb][tb]);
		int bminn=min(bmin[lb][tb],bmin[pb][tb]);
		
		int ans=MIN;
		
		ans=max(ans,amaxx*(amaxx>=0?bminn:bmaxx));
		ans=max(ans,aminn*(aminn>=0?bminn:bmaxx));
		if(afaxx!=MIN)ans=max(ans,afaxx*(afaxx>=0?bminn:bmaxx));
		if(azinn!=MAX)ans=max(ans,azinn*(azinn>=0?bminn:bmaxx));
		
		printf("%lld\n",ans);
	}
	return 0;
}