线段树85pts
查看原帖
线段树85pts
756747
Ithea686楼主2023/10/18 22:10

求告诉缺了什么情况还是哪写错了.

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

const int inf=999999999;
int n,m,k;
int a[100005],b[100005];
int s1[400005],s2[400005];
int mx1[400005],mx2[400005];
int mi1[400005],mi2[400005];
int natmx[400005]/*>0中最小的*/,natmi[400005]/*<0中最大的*/;

void build1(int k,int l,int r){
	if (l==r) 
		{natmx[k]=a[l]>=0?a[l]:inf;natmi[k]=a[l]<=0?a[l]:-inf;return s1[k]=a[l],mx1[k]=mi1[k]=a[l], void();}
	int mid=l+r>>1;
	build1(k<<1,l,mid);
	build1(k<<1|1,mid+1,r);
	mx1[k]=max(mx1[k<<1],mx1[k<<1|1]);
	mi1[k]=min(mi1[k<<1],mi1[k<<1|1]);
	natmx[k]=min(natmx[k<<1],natmx[k<<1|1]);
	natmi[k]=max(natmi[k<<1],natmi[k<<1|1]);
}

void build2(int k,int l,int r){
	if (l==r) 
		return s2[k]=b[l],mx2[k]=mi2[k]=b[l], void();
	int mid=l+r>>1;
	build2(k<<1,l,mid);
	build2(k<<1|1,mid+1,r);
	mx2[k]=max(mx2[k<<1],mx2[k<<1|1]);
	mi2[k]=min(mi2[k<<1],mi2[k<<1|1]);
}

int mx_fun(int k,int l,int r,int x,int y){
	if (l>=x&&r<=y) return mx1[k];
	int mid=l+r>>1;
	int re=-inf;
	if (mid>=x) re=max(re,mx_fun(k<<1,l,mid,x,y));
	if (mid<y) re=max(re,mx_fun(k<<1|1,mid+1,r,x,y));
	return re; 
}

int mi_fun(int k,int l,int r,int x,int y){
	if (l>=x&&r<=y) return mi1[k];
	int mid=l+r>>1;
	int re=inf;
	if (mid>=x) re=min(re,mi_fun(k<<1,l,mid,x,y));
	if (mid<y) re=min(re,mi_fun(k<<1|1,mid+1,r,x,y));
	return re;
}

int mx_fun2(int k,int l,int r,int x,int y){
	if (l>=x&&r<=y) return mx2[k];
	int mid=l+r>>1;
	int re=-inf;
	if (mid>=x) re=max(re,mx_fun2(k<<1,l,mid,x,y));
	if (mid<y) re=max(re,mx_fun2(k<<1|1,mid+1,r,x,y));
	return re; 
}

int mi_fun2(int k,int l,int r,int x,int y){
	if (l>=x&&r<=y) return mi2[k];
	int mid=l+r>>1;
	int re=inf;
	if (mid>=x) re=min(re,mi_fun2(k<<1,l,mid,x,y));
	if (mid<y) re=min(re,mi_fun2(k<<1|1,mid+1,r,x,y));
	return re;
}

int nat_min(int k,int l,int r,int x,int y){//>0中最小 
	if (l>=x&&r<=y) return natmx[k];
	int mid=l+r>>1;
	int re=inf;
	if (mid>=x) re=min(re,nat_min(k<<1,l,mid,x,y));
	if (mid<y) re=min(re,nat_min(k<<1|1,mid+1,r,x,y));
	return re;
}

int nat_max(int k,int l,int r,int x,int y){//<0中最大 
	if (l>=x&&r<=y) return natmi[k];
	int mid=l+r>>1;
	int re=-inf;
	if (mid>=x) re=max(re,nat_max(k<<1,l,mid,x,y));
	if (mid<y) re=max(re,nat_max(k<<1|1,mid+1,r,x,y));
	return re; 
}

int main(){
//	freopen("game.in","r",stdin);
//	freopen("game.out","w",stdout);
	memset(s1,-127,sizeof s1);
	memset(s2,127,sizeof s2);
	scanf("%d%d%d",&n,&m,&k);
	for (int i=1;i<=n;i++) scanf("%d",a+i);
	for (int i=1;i<=m;i++) scanf("%d",b+i);
	build1(1,1,n);
	build2(1,1,m);
	for (int i=1;i<=k;i++){
		int l1,l2,r1,r2;
		scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
		int ymx=mx_fun2(1,1,m,l2,r2),ymi=mi_fun2(1,1,m,l2,r2);
		if (ymx>=0&&ymi>=0){
			long long ans2=mx_fun(1,1,n,l1,r1);
			if (ans2>=0)
				printf("%lld\n",(long long)min(ymx,ymi)*mx_fun(1,1,n,l1,r1));
			else 
				printf("%lld\n",(long long)max(ymx,ymi)*mx_fun(1,1,n,l1,r1));
		}
		else if (ymx<=0&&ymi<=0){
			long long ans1=mi_fun(1,1,n,l1,r1);
			if (ans1<=0)
				printf("%lld\n",(long long)max(ymx,ymi)*mi_fun(1,1,n,l1,r1));
			else 
				printf("%lld\n",(long long)min(ymx,ymi)*mi_fun(1,1,n,l1,r1));
		}
		else {
			printf("%lld\n",max((long long)ymx*nat_max(1,1,n,l1,r1),(long long)ymi*nat_min(1,1,n,l1,r1)));
		}
	}
	
	return 0;
}
2023/10/18 22:10
加载中...