线段树做法 一般点 18号 过不去
查看原帖
线段树做法 一般点 18号 过不去
1125784
shuidianfei楼主2024/4/13 17:32

求大佬支支招 18 24 25 31 32 38 39 40不过(基本上不是特殊性质就会wa,但是19 20又能过) 代码内有注释

#include<bits/stdc++.h>
#define maxmax aa//正max 
#define maxmin ai//正min 
#define minmax ia//负max 
#define minmin ii//负min 
#define kongjian 110000
#define mid ((l+r)>>1)
#define ln (num<<1)
#define rn ((num<<1)+1)
using namespace std;
long long aa[4*kongjian][2],ai[4*kongjian][2],ia[4*kongjian][2],ii[4*kongjian][2],in[kongjian][2],n,m,q,l1,r1,l2,r2;
bitset<2> zero[kongjian*4];//0代表区间内没有0 1代表区间内有0
//axis代表行列 0 行 1 列 
void mix(int f,int s1,int s2,int axis){//把s1,s2汇总到f索引的格子里 
	aa[f][axis]=max(aa[s1][axis],aa[s2][axis]);
	if(ai[s1][axis]==0 || ai[s2][axis]==0)
		ai[f][axis]=max(ai[s1][axis],ai[s2][axis]);
	else
		ai[f][axis]=min(ai[s1][axis],ai[s2][axis]);
	ii[f][axis]=min(ii[s1][axis],ii[s2][axis]);
	if(ia[s1][axis]==0 || ia[s2][axis]==0)
		ia[f][axis]=min(ia[s1][axis],ia[s2][axis]);
	else
		ia[f][axis]=max(ia[s1][axis],ia[s2][axis]);
	zero[f][axis]=max(zero[s1][axis],zero[s2][axis]);
}
void build(int l,int r,int num,int axis){//建树 
	if(l==r){
		if(in[l][axis]==0){
			aa[num][axis]=ai[num][axis]=0;
			ia[num][axis]=ii[num][axis]=0;
			zero[num][axis]=1;
		}
		if(in[l][axis]<0){
			ia[num][axis]=ii[num][axis]=in[l][axis];
			aa[num][axis]=ai[num][axis]=0;
			zero[num][axis]=0;
		}
		if(in[l][axis]>0){
			aa[num][axis]=ai[num][axis]=in[l][axis];
			ia[num][axis]=ii[num][axis]=0;
			zero[num][axis]=0;
		}
	}
	else{
		build(l,mid,ln,axis);
		build(mid+1,r,rn,axis);
		mix(num,ln,rn,axis);
	}
}
void ask(int l,int r,int al,int ar,int num,int axis){//l r大区间,al ar查询
	//cout<<"l "<<l<<"r "<<r<<"al "<<al<<"ar "<<ar<<"num "<<num<<"   axis "<<axis<<endl;
	if(al<=l && ar>=r){	//cout<<"l "<<l<<"r "<<r<<"al "<<al<<"ar "<<ar<<"num "<<num<<"   axis "<<axis<<endl;
		mix(0,0,num,axis);
	}
	else{
		if(al<=mid)
			ask(l,mid,al,ar,ln,axis);
		if(ar>=mid+1)
			ask(mid+1,r,al,ar,rn,axis);
	}
}
void start(){//初始化 
	aa[0][0]=0;
	ai[0][0]=0;
	aa[0][1]=0;
	ai[0][1]=0;
	ia[0][0]=0;
	ii[0][0]=0;
	ia[0][1]=0;
	ii[0][1]=0;
	zero[0][0]=0;
	zero[0][1]=0;
}
long long js(){//计算 (+-0 +- 表示有+ - 0的区间)×(有+ -的区间)
	if(aa[0][0]!=0 && ii[0][0]!=0 && zero[0][0]==1){//+-0
		if(aa[0][1]!=0 && ii[0][1]!=0){//+-
			//cout<<"+-0 +-"<<endl;
			return 0;
			}
		else if(zero[0][1]==1){//+0 -0 0
			//cout<<"+-0 (+0 -0 0)"<<endl;
			return 0;
			}
		else if(aa[0][1]!=0){//+
			//cout<<"+-0 +"<<endl;
			return aa[0][0]*ai[0][1];
			}
		else if(ii[0][1]!=0){//-
			//cout<<"+-0 -"<<endl;
			return ii[0][0]*ia[0][1];
			}
	}
	else if(aa[0][0]!=0 && ii[0][0]!=0){//+-
		if(zero[0][1]==1){//+0 -0 0
			//cout<<"+- (+0 -0 0)"<<endl;
			return 0;
			}
		else if(aa[0][1]!=0 && ii[0][1]!=0){//+-0 +-
			//cout<<"+- (+-0 +-)"<<endl;
			return max(ai[0][0]*ii[0][1],ia[0][0]*aa[0][1]);
			}
		else if(aa[0][1]!=0){//+
			//cout<<"+- +"<<endl;
			return aa[0][0]*ai[0][1];
			}
		else if(ii[0][1]!=0){//-
			//cout<<"+- -"<<endl;
			return ii[0][0]*ia[0][1];
			}
	}
	else if(aa[0][0]!=0 && zero[0][0]==1){//+0
		if(aa[0][1]!=0 && ii[0][1]==0 && zero[0][1]==0){//+
			//cout<<"+0 +"<<endl;
			return aa[0][0]*ai[0][1];
			}
		else{
			//cout<<"+0 (+-0 +- +0 -0 - 0)"<<endl;
			return 0;
			}
	}
	else if(ii[0][0]!=0 && zero[0][0]==1){//-0
		if(ii[0][1]!=0 && aa[0][1]==0 && zero[0][1]==0){//-
			//cout<<"-0 -"<<endl;
			return ii[0][0]*ia[0][1];
			}
		else{
			//cout<<"-0 (+-0 +- +0 -0 + 0"<<endl;
			return 0;
		}
	}
	else if(aa[0][0]!=0){//+
		if(ii[0][1]!=0){//+-0 +- -0 -
			//cout<<"+ (+-0 +- -0 0)"<<endl;
			return ai[0][0]*ii[0][1];
			}
		else if(aa[0][1]!=0 && zero[0][1]==0){//+
			//cout<<"+ +"<<endl;
			return aa[0][0]*ai[0][1];
			}
		else if(ii[0][0]==0 && zero[0][1]==1){//+0 0
			//cout<<"+ (+0 0)"<<endl;
			return 0;
			}
	}
	else if(ii[0][0]!=0){//-
		if(aa[0][1]!=0){//+-0 +- +0 +
			//cout<<"- (+-0 +- +0 +)"<<endl;
			return ia[0][0]*aa[0][1];
			}
		else if(ii[0][1]!=0 && zero[0][1]==1){//-
			//cout<<"- -"<<endl;
			return ii[0][0]*ia[0][1];
			}
		else if(aa[0][0]==0 && zero[0][1]==1){//-0 0
			//cout<<"- (-0 0)"<<endl;
			return 0;
			}
	}
	else if(aa[0][0]!=0 && ii[0][0]!=0 && zero[0][0]==1){//0
		//cout<<"00"<<endl;
		return 0;
		}
}
void output(){//中间过程输出 
	cout<<"      ";
	for(int i=0;i<=pow(2,log(n)+2);i++)
		printf("%3d",i);
	printf("\nmaxmax");
	for(int i=0;i<=pow(2,log(n)+2);i++)
		printf("%3ld",aa[i][0]);
	printf("\nmaxmin");
	for(int i=0;i<=pow(2,log(n)+2);i++)
		printf("%3lld",ai[i][0]);
	printf("\nminmax");
	for(int i=0;i<=pow(2,log(n)+2);i++)
		printf("%3lld",ia[i][0]);
	printf("\nminmin");
	for(int i=0;i<=pow(2,log(n)+2);i++)
		printf("%3lld",ii[i][0]);
	printf("\nzero  ");
	for(int i=0;i<=pow(2,log(n)+2);i++)
		printf("%3d",(zero[i][0]?1:0));
	printf("\n");
	printf("\nmaxmax");
	for(int i=0;i<=pow(2,log(m)+2);i++)
		printf("%3lld",aa[i][1]);
	printf("\nmaxmin");
	for(int i=0;i<=pow(2,log(m)+2);i++)
		printf("%3lld",ai[i][1]);
	printf("\nminmax");
	for(int i=0;i<=pow(2,log(m)+2);i++)
		printf("%3lld",ia[i][1]);
	printf("\nminmin");
	for(int i=0;i<=pow(2,log(m)+2);i++)
		printf("%3lld",ii[i][1]);
	printf("\nzero  ");
	for(int i=0;i<=pow(2,log(m)+2);i++)
		printf("%3d",(zero[i][1]?1:0));
	printf("\n");
}
int main(){
	cin>>n>>m>>q;
	for(int i=1;i<=n;i++)
		scanf("%lld",&in[i][0]);
	for(int i=1;i<=m;i++)
		scanf("%lld",&in[i][1]);
	build(1,n,1,0);
	build(1,m,1,1);
	//output();
	for(int i=1;i<=q;i++){
		scanf("%lld%lld%lld%lld",&l1,&r1,&l2,&r2);
		start();//初始化
		ask(1,n,l1,r1,1,0);
		ask(1,m,l2,r2,1,1);
		//output();
		printf("%lld\n",js());
	}
	return 0;
}
2024/4/13 17:32
加载中...