提交记录

代码写的确实太繁琐了，但蒟蒻真找不出来哪错了 求助QAQ （写了8个ST表，有俩是没用的）

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-'){
			f=-1;
		}
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<3)+(x<<1)+ch-'0';
		ch=getchar();
	}
	return x*f;
}

const int N=100010,M=20,inf=1e9+1; 
int n,m,q;
int a[N],b[N];

int astmax[N][M],astmin[N][M],astfmax[N][M],astzmin[N][M];
int bstmax[N][M],bstmin[N][M],bstfmax[N][M],bstzmin[N][M];

int lg[N];

int l1,r1,l2,r2;
ll ansx,ansy;
void work1(){//暴力分部分 
	while(q--){
		l1=read();
		r1=read();
		l2=read();
		r2=read();
		ansx=-1e18;
		for(int i=l1;i<=r1;i++){
			ansy=1e18;
			for(int j=l2;j<=r2;j++){
				ansy=min(ansy,(ll)a[i]*b[j]);
			}
			ansx=max(ansx,ansy);
		}
		printf("%lld\n",ansx);
	}
}

void pre1(){
	lg[1]=0;
	for(int i=2;i<=max(n,m);i++){
		lg[i]=lg[i/2]+1;
	}
}

void prea(){
	for(int i=1;i<=n;i++){
		astmax[i][0]=astmin[i][0]=a[i];
		if(a[i]>=0){
			astzmin[i][0]=a[i];
			astfmax[i][0]=-inf;
		}
		else{
			astzmin[i][0]=inf;
			astfmax[i][0]=a[i];
		} 
	}
	for(int i=1;i<=20;i++){
		for(int j=1;j+(1<<i)-1<=n;j++){
			astmax[j][i]=max(astmax[j][i-1],astmax[j+(1<<(i-1))][i-1]);
			astmin[j][i]=min(astmin[j][i-1],astmin[j+(1<<(i-1))][i-1]);
			astfmax[j][i]=max(astfmax[j][i-1],astfmax[j+(1<<(i-1))][i-1]);
			astzmin[j][i]=min(astzmin[j][i-1],astzmin[j+(1<<(i-1))][i-1]);
		}
	}
}

void preb(){
	for(int i=1;i<=m;i++){
		bstmax[i][0]=bstmin[i][0]=b[i];
		if(b[i]>=0){
			bstzmin[i][0]=b[i];
			bstfmax[i][0]=-inf;
		}
		else{
			bstzmin[i][0]=inf;
			bstfmax[i][0]=b[i];
		} 
	}
	for(int i=1;i<=20;i++){
		for(int j=1;j+(1<<i)-1<=m;j++){
			bstmax[j][i]=max(bstmax[j][i-1],bstmax[j+(1<<(i-1))][i-1]);
			bstmin[j][i]=min(bstmin[j][i-1],bstmin[j+(1<<(i-1))][i-1]);
			bstfmax[j][i]=max(bstfmax[j][i-1],bstfmax[j+(1<<(i-1))][i-1]);
			bstzmin[j][i]=min(bstzmin[j][i-1],bstzmin[j+(1<<(i-1))][i-1]);
		}
	}
}

int query(int l,int r,int ab,int opt){//ab=1->A数组   ab=2->B数组 
	int z=lg[r-l+1];//z=1
	if(ab==1){
		if(opt==1){
			return min(astmin[l][z],astmin[r-(1<<z)+1][z]);
		}
		if(opt==2){ //astmax[5][1],astmax[5][1]
			return max(astmax[l][z],astmax[r-(1<<z)+1][z]);
		}
		if(opt==3){
			return max(astfmax[l][z],astfmax[r-(1<<z)+1][z]);
		}
		if(opt==4){
			return min(astzmin[l][z],astzmin[r-(1<<z)+1][z]);
		}
	}
	else if(ab==2){
		if(opt==1){
			return min(bstmin[l][z],bstmin[r-(1<<z)+1][z]);
		}
		if(opt==2){
			return max(bstmax[l][z],bstmax[r-(1<<z)+1][z]);
		}
		if(opt==3){
			return max(bstfmax[l][z],bstfmax[r-(1<<z)+1][z]);
		}
		if(opt==4){
			return min(bstzmin[l][z],bstzmin[r-(1<<z)+1][z]);
		}
	}
}

int main(){
	//freopen("game.in","r",stdin);
	//freopen("game.out","w",stdout);
	n=read();
	m=read();
	q=read();
	for(int i=1;i<=n;i++){
		a[i]=read();
	}
	for(int i=1;i<=m;i++){
		b[i]=read();
	}
	if(n<=1000&&m<=1000){//暴力部分 
		work1();
		return 0;
	}
	else{
		pre1();//预处理log 
		prea();//预处理两个数组 
		preb();
		while(q--){
			l1=read();
			r1=read();
			l2=read();
			r2=read();
			ll ans=0;
			
			int amin=query(l1,r1,1,1);//最小值 
			int amax=query(l1,r1,1,2);//最大值
			int afmax=query(l1,r1,1,3);//负数最大值 
			int azmin=query(l1,r1,1,4);//正数最小值 
			int bmin=query(l2,r2,2,1); 
			int bmax=query(l2,r2,2,2); 
			int bfmax=query(l2,r2,2,3);
			int bzmin=query(l2,r2,2,4);
			
			if(bmin>=0){ //如果B全正 
				if(amax<0){
					ans=(ll)amax*bmax;
				}
				else{
					ans=(ll)bmin*amax;
				}	
			}
			else if(bmax<=0){ //B全负 
				if(amin<0){
					ans=(ll)amin*bmax;
				}
				else{
					ans=(ll)bmin*amin;
				}
			}
			else{ //B有正有负 
				ans=max((ll)azmin*bmin,(ll)afmax*bmax);
			}
			printf("%lld\n",ans);
		}
	}
	return 0;
}