3 个关注。

https://www.luogu.com.cn/record/92850558

死活调不出来，拍了几百万组也拍不出来。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
// ======Input data==========
int n,m,q;
int a[maxn];
int b[maxn];
// =======ST========
// ST_a
int st_a_max[20][maxn];
int st_a_min[20][maxn];
int st_a_abs_min_dyl[20][maxn];
int st_a_abs_max_xyl[20][maxn];
// ST_b
int st_b_max[20][maxn];
int st_b_min[20][maxn];
// init_log2
int _log2[maxn];
// get st
int getmax_a(int l,int r)
{
	int _lg=_log2[r-l+1];
	return max(st_a_max[_lg][l],st_a_max[_lg][r-(1<<_lg)+1]);
}
int getmin_a(int l,int r)
{
	int _lg=_log2[r-l+1];
	return min(st_a_min[_lg][l],st_a_min[_lg][r-(1<<_lg)+1]);
}
int getmin_a_abs_dyl(int l,int r)
{
	int _lg=_log2[r-l+1];
	return min(st_a_abs_min_dyl[_lg][l],st_a_abs_min_dyl[_lg][r-(1<<_lg)+1]);
}
int getmax_a_abs_xyl(int l,int r)
{
	int _lg=_log2[r-l+1];
	return max(st_a_abs_max_xyl[_lg][l],st_a_abs_max_xyl[_lg][r-(1<<_lg)+1]);
}
int getmax_b(int l,int r)
{
	int _lg=_log2[r-l+1];
	return max(st_b_max[_lg][l],st_b_max[_lg][r-(1<<_lg)+1]);
}
int getmin_b(int l,int r)
{
	int _lg=_log2[r-l+1];
	return min(st_b_min[_lg][l],st_b_min[_lg][r-(1<<_lg)+1]);
}
int main()
{
	// Input
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		st_a_max[0][i]=a[i];
		st_a_min[0][i]=a[i];
		st_a_abs_min_dyl[0][i]=a[i];
		if(a[i]<0)st_a_abs_min_dyl[0][i]=2e9;
		st_a_abs_max_xyl[0][i]=a[i];
		if(a[i]>0)st_a_abs_max_xyl[0][i]=-2000000000;
	}
	for(int i=1;i<=m;i++)
	{
		scanf("%d",&b[i]);
		st_b_max[0][i]=b[i];
		st_b_min[0][i]=b[i];
	}
	// Init
	for(int i=2;i<maxn;i++)_log2[i]=_log2[i>>1]+1;
	for(int i=1;i<=19;i++)
	{
		for(int j=1;j<=n-(1<<i)+1;j++)
		{
			st_a_max[i][j]=max(st_a_max[i-1][j],st_a_max[i-1][j+(1<<i-1)]);
		}
		for(int j=1;j<=n-(1<<i)+1;j++)
		{
			st_a_min[i][j]=min(st_a_min[i-1][j],st_a_min[i-1][j+(1<<i-1)]);
		}
		for(int j=1;j<=n-(1<<i)+1;j++)
		{
			st_a_abs_min_dyl[i][j]=min(st_a_abs_min_dyl[i-1][j],st_a_abs_min_dyl[i-1][j+(1<<i-1)]);
		}
		for(int j=1;j<=n-(1<<i)+1;j++)
		{
			st_a_abs_max_xyl[i][j]=max(st_a_abs_max_xyl[i-1][j],st_a_abs_max_xyl[i-1][j+(1<<i-1)]);
		}
		for(int j=1;j<=m-(1<<i)+1;j++)
		{
			st_b_max[i][j]=max(st_b_max[i-1][j],st_b_max[i-1][j+(1<<i-1)]);
		}
		for(int j=1;j<=m-(1<<i)+1;j++)
		{
			st_b_min[i][j]=min(st_b_min[i-1][j],st_b_min[i-1][j+(1<<i-1)]);
		}
	}
	int l1,r1,l2,r2;
	while(q--)
	{
		scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
		ll max_a=getmax_a(l1,r1);
		ll min_a=getmin_a(l1,r1);
		ll min_a_abs_dyl=getmin_a_abs_dyl(l1,r1);
		ll max_a_abs_xyl=getmax_a_abs_xyl(l1,r1);
		ll max_b=getmax_b(l2,r2);
		ll min_b=getmin_b(l2,r2);
		ll res=0;
		if(max_b<0)
		{
			if(min_a>=0)
			{
				res=1ll*min_a*1ll*min_b;
			}
			else
			{
				res=1ll*min_a*1ll*max_b;
			}
		}
		else if(min_b>=0)
		{
			if(max_a>=0)
			{
				res=1ll*max_a*1ll*min_b;
			}
			else
			{
				res=1ll*max_a*1ll*max_b;
			}
		}
		else
		{
			if(max_a_abs_xyl==-2000000000)
			{
				res=1ll*min_a_abs_dyl*1ll*min_b;
			}
			if(min_a_abs_dyl==2e9)
			{
				res=1ll*max_a_abs_xyl*1ll*max_b;
			}
			else res=max(1ll*max_a_abs_xyl*1ll*max_b,1ll*min_a_abs_dyl*1ll*min_b);
		}
		printf("%lld\n",res);
	}
	return 0;	
}