记录

不明白　这复杂度不是O(qlogn)吗？n,q<=1e5

#include<bits/stdc++.h>
#define lc p<<1
#define rc p<<1|1
#define M(p,t) tr[p][t].M
#define m(p,t) tr[p][t].m
#define l(p,t) tr[p][t].l
#define r(p,t) tr[p][t].r
#define up(p,t) M(p,t)=max(M(lc,t),M(rc,t));m(p,t)=min(m(lc,t),m(rc,t))
#define int ll
#define intt int
using namespace std;
typedef long long ll;
const intt N=1e5+1,inf=1e9+5;
struct SegmentTree{
	int p,M,m,l,r;	
}tr[4*N][4];//0:A 1:B 2:A(-) 3:A(+)
int a[N],b[N];
bool flag1[4*N];
void build(int p,int l,int r,int t)
{
    tr[p][t]={p,-inf,inf,l,r};
	if(l==r) 
	{
	    if(!t) M(p,t)=m(p,t)=a[l];
	    else if(t==1) M(p,1)=m(p,1)=b[l];
	    else if(t==2)
	    {
	       if(a[l]<0) M(p,t)=m(p,t)=a[l];	
	       else 
		   {
		   		if(a[l]==0) flag1[p]=1;
				M(p,t)=-inf,m(p,t)=inf;
		   }
	    }
	    else
	    {
	        if(a[l]>0) M(p,t)=m(p,t)=a[l];
	        else 
			{
				//if(a[l]==0) flag1[p]=1;
				M(p,t)=-inf,m(p,t)=inf;
			}
	    }
	    return;
	}
	int mid=l+(r-l)/2;
	build(lc,l,mid,t);
	build(rc,mid+1,r,t);
	up(p,t);
	if(t==2) flag1[p]=flag1[lc]|flag1[rc];
}
bool flag;
pair<int,int> query(int p,int l,int r,int t)
{
    if(l(p,t)>r||r(p,t)<l) return {-inf,inf};
    if(l(p,t)>=l&&r(p,t)<=r) 
	{
		if(t==2) flag|=flag1[p];
		return {M(p,t),m(p,t)};
	}
    return {max(query(lc,l,r,t).first,query(rc,l,r,t).first),min(query(lc,l,r,t).second,query(rc,l,r,t).second)};
}
int n,mm,q;
signed main()
{
	//freopen("game4.in","r",stdin);
	//freopen("g4.ans","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>mm>>q;
	for(int i=1;i<=n;i++) 
	{
	    cin>>a[i];
	   // if(!a[i]) flag1[i]=1;
	}
	for(int i=1;i<=mm;i++)  cin>>b[i];
	build(1,1,n,0);
	build(1,1,n,2);
	build(1,1,mm,1);
	build(1,1,n,3);
	while(q--)
	{
		int l1,r1,l2,r2;
		cin>>l1>>r1>>l2>>r2;
		pair<int,int> A=query(1,l1,r1,0);
		pair<int,int> B=query(1,l2,r2,1);
		int AM=A.first,BM=B.first,Am=A.second,Bm=B.second;
		//cout<<AM<<' '<<Am<<' '<<BM<<' '<<Bm<<endl;
		if(Bm>0&&AM>0) 
		{
		    //if(!AM) cout<<0<<'\n';
		    //else if(AM<0&&Am<0) cout<<AM*BM<<'\n';
		     cout<<AM*Bm<<'\n';
		}
		else if(AM<0&&BM>0)
		{
		    cout<<AM*BM<<'\n';
		}
		else if(Am>0&&Bm<0) cout<<Am*Bm<<'\n';
		else if(BM<0&&Am<0) cout<<Am*BM<<'\n';
		else if(Am<0&&Bm<0&&BM>0&&AM>0) 
		{
		    //if(flag1<=r1&&flag1>=l1 ) cout<<0<<'\n';
			flag=0;
			pair<int,int> RA=query(1,l1,r1,2);
			//cout<<"flag:"<<flag<<endl;
			if(flag) cout<<0<<'\n';        
			else
			{
			    int RAm=RA.first; //abs最小负数
			    int ZAm=query(1,l1,r1,3).second;//abs最小正数
			    cout<<max(RAm*BM,ZAm*Bm)<<'\n';    
			} 
		}
		else cout<<0<<'\n';
	}
 	return 0;
}