[CSP-S 2022] 策略游戏
45pts

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+6,M=20;
int n,m,q,amax[N][M],amin[N][M],bmax[N][M],bmin[N][M],afmx[N][M],azmn[N][M],f[5];
int get(int a[N][M],int l,int r,int op){
	int len=log2(r-l+1);
	if(op) return max(a[l][len],a[r-(1<<len)+1][len]);
	return min(a[l][len],a[r-(1<<len)+1][len]);
}
int cho(int x,int p,int q){
	if(x>0) return x*p;
	return x*q;
}
signed main(){
	cin>>n>>m>>q;
	for(int i=1,a;i<=n;i++){
		cin>>a;
		amax[i][0]=amin[i][0]=a;
		azmn[i][0]=a>0?a:LONG_LONG_MAX;
		afmx[i][0]=a<=0?a:LONG_LONG_MIN;
	}
	for(int i=1,b;i<=m;i++){
		cin>>b;
		bmin[i][0]=bmax[i][0]=b;
	}
	for(int j=1;j<=16;j++){
		for(int i=1;i+(1<<j)-1<=n;i++){
			amax[i][j]=max(amax[i][j-1],amax[i+(1<<j-1)][j-1]);
			amin[i][j]=min(amin[i][j-1],amin[i+(1<<j-1)][j-1]);
			azmn[i][j]=min(azmn[i][j-1],azmn[i+(1<<j-1)][j-1]);
			afmx[i][j]=max(afmx[i][j-1],afmx[i+(1<<j-1)][j-1]);
		}
	}
	for(int j=1;j<=16;j++){
		for(int i=1;i+(1<<j)-1<=m;i++){
			bmax[i][j]=max(bmax[i][j-1],bmax[i+(1<<j-1)][j-1]);
			bmin[i][j]=min(bmin[i][j-1],bmin[i+(1<<j-1)][j-1]);
		}
	}
	while(q--){
		int l1,r1,l2,r2;
		cin>>l1>>r1>>l2>>r2;
		f[1]=get(amax,l1,r1,1);
		f[2]=get(amin,l1,r1,0);
		f[3]=get(azmn,l1,r1,0);
		f[4]=get(afmx,l1,r1,1);
		int maxx=get(bmax,l2,r2,1),minn=get(bmin,l2,r2,0);
		int ans=LONG_LONG_MIN;
		for(int i=1;i<=4;i++){
			ans=max(ans,cho(f[i],minn,maxx));
		}
		cout<<ans<<'\n';
	} 
}

40pts

#include<bits/stdc++.h>
#define int long long
#define INF 1000000001
using namespace std;
const int N=1e5+6,M=20;
int n,m,q,amax[N][M],amin[N][M],bmax[N][M],bmin[N][M],afmx[N][M],azmn[N][M],f[5];
int get(int a[N][M],int l,int r,int op){
	int len=log2(r-l+1);
	if(op) return max(a[l][len],a[r-(1<<len)+1][len]);
	return min(a[l][len],a[r-(1<<len)+1][len]);
}
int cho(int x,int p,int q){
	if(x>0) return x*p;
	return x*q;
}
signed main(){
	cin>>n>>m>>q;
	for(int i=1,a;i<=n;i++){
		cin>>a;
		amax[i][0]=amin[i][0]=a;
		azmn[i][0]=a>0?a:INF;
		afmx[i][0]=a<=0?a:-INF;
	}
	for(int i=1,b;i<=m;i++){
		cin>>b;
		bmin[i][0]=bmax[i][0]=b;
	}
	for(int j=1;j<=18;j++){
		for(int i=1;i+(1<<j)-1<=n;i++){
			amax[i][j]=max(amax[i][j-1],amax[i+(1<<j-1)][j-1]);
			amin[i][j]=min(amin[i][j-1],amin[i+(1<<j-1)][j-1]);
			azmn[i][j]=min(azmn[i][j-1],azmn[i+(1<<j-1)][j-1]);
			afmx[i][j]=max(afmx[i][j-1],afmx[i+(1<<j-1)][j-1]);
		}
	}
	for(int j=1;j<=18;j++){
		for(int i=1;i+(1<<j)-1<=m;i++){
			bmax[i][j]=max(bmax[i][j-1],bmax[i+(1<<j-1)][j-1]);
			bmin[i][j]=min(bmin[i][j-1],bmin[i+(1<<j-1)][j-1]);
		}
	}
	while(q--){
		int l1,r1,l2,r2;
		cin>>l1>>r1>>l2>>r2;
		f[1]=get(amax,l1,r1,1);
		f[2]=get(amin,l1,r1,0);
		f[3]=get(azmn,l1,r1,0);
		f[4]=get(afmx,l1,r1,1);
		int maxx=get(bmax,l2,r2,1),minn=get(bmin,l2,r2,0);
		int ans=LONG_LONG_MIN;
		for(int i=1;i<=4;i++) ans=max(ans,cho(f[i],minn,maxx));
		cout<<ans<<'\n';
	} 
}