求大佬支支招 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;
}