一个疑问
查看原帖
一个疑问
304458
ZHUHK楼主2022/11/1 13:15

max1,max2 0上最大最小 min1,min2 0下最大最小 z 有无0 请问分类讨论错在了哪里

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL INF=1e18;
const int N=1e6+10;
int n,m,q;
LL a[N],b[N];
struct Tree
{
	int l,r;
	LL max1,max2,min1,min2,z;
}tr1[N<<2],tr2[N<<2];
void output(Tree t){
	puts(" ");
	cout<<t.max1<<" "<<t.min1<<endl;
	cout<<t.max2<<" "<<t.min2<<endl;
	cout<<t.z<<endl;
}

Tree getnode(int l,int r){
	return (Tree){l,r,0,-INF,INF,0,0};
}
void pushup(Tree &t,Tree l,Tree r){
	t.max1=max(l.max1,r.max1);
	t.max2=max(l.max2,r.max2);
	t.min1=min(l.min1,r.min1);
	t.min2=min(l.min2,r.min2);
	t.z=l.z|r.z;
}
void build(int u,int l,int r,Tree tr[],LL d[]){
	tr[u]=getnode(l,r);
	if(l==r){
		if(d[l]>0){
			tr[u].max1=tr[u].min1=d[l];
			tr[u].max2=-0x3f3f3f3f,tr[u].min2=0;tr[u].z=0;
		} 
		if(d[l]<0){
			tr[u].max1=0,tr[u].min1=0x3f3f3f3f;
			tr[u].max2=tr[u].min2=d[l];tr[u].z=0;
		}
		if(d[l]==0) {
			tr[u].z=1;
			tr[u].max2=-0x3f3f3f3f,tr[u].min2=0;
			tr[u].max1=0,tr[u].min1=0x3f3f3f3f;
		}
	
		return ;
	}
	int mid=(l+r)>>1;
	build(u<<1,l,mid,tr,d);build(u<<1|1,mid+1,r,tr,d);
	pushup(tr[u],tr[u<<1],tr[u<<1|1]);	
}

Tree query(Tree tr[],int u,int l,int r){
	if(l<=tr[u].l&&tr[u].r<=r) return tr[u];
	int mid=(tr[u].l+tr[u].r)>>1;
	Tree ret=getnode(0,0);
	if(l<=mid) pushup(ret,ret,query(tr,u<<1,l,r));
	if(r>mid) pushup(ret,ret,query(tr,u<<1|1,l,r));
	return ret;
}
int main(){
//	freopen("game3.in","r",stdin);
	scanf("%d%d%d",&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]);
	
	build(1,1,n,tr1,a);build(1,1,m,tr2,b);
	
	while(q--){
		int l1,r1,l2,r2;
		scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
		Tree t1=query(tr1,1,l1,r1),t2=query(tr2,1,l2,r2);
		
//		output(t1);output(t2);
		LL ans=-2e18;
		if(t1.max1!=INF){
			if(t2.min2!=0) {ans=max(ans,1ll*t1.max1*t2.min2);}
			else if(t2.z==1) {ans=max(1ll*0,ans);}
			else if(t2.min1!=INF) {ans=max(1ll*t1.max1*t2.min1,ans);}
		}
		if(t1.min1!=INF){
			if(t2.min2!=0) {ans=max(ans,1ll*t1.min1*t2.min2);}
			else if(t2.z==1) {ans=max(1ll*0,ans);}
			else if(t2.min1!=INF) {ans=max(1ll*t1.min1*t2.min1,ans);}
		}
		if(t1.min2!=0) {
			if(t2.max1!=0) ans=max(ans,1ll*t1.min2*t2.max1);
			else if(t2.z==1) ans=max(1ll*0,ans);
			else if(t2.max2!=-INF) ans=max(ans,1ll*t1.min2*t2.max2);
		}
		if(t1.max2!=INF){ 
			if(t2.max1!=0) ans=max(ans,1ll*t1.max2*t2.max1);
			else if(t2.z==1) ans=max(1ll*0,ans);
			else if(t2.max2!=-INF) ans=max(ans,1ll*t1.max2*t2.max2); 
		}
		cout<<ans<<endl;
	}
	return 0;
}
2022/11/1 13:15
加载中...