我有一个朋友(真的有朋友),他在洛谷上AC,但是到别的网站测有90分的,更有甚者50分,但我们都找不出有什么问题(我没认真找),所以想让大佬们帮忙看看有啥问题。
#include <bits/stdc++.h>
using namespace std;
#define int long long
int a[100005],b[100005],n,m,asks,lg2[100005];
struct st{
int f11[100005][25],f21[100005][25],f12[100005][25],f22[100005][25],p[100005];
void init(){
memset(f11,-0x3f,sizeof(f11));
memset(f21,0x3f,sizeof(f21));
memset(f12,-0x3f,sizeof(f12));
memset(f22,0x3f,sizeof(f22));
for(int i=1;i<=n;i++){if(p[i]==0)f11[i][0]=f12[i][0]=f21[i][0]=f22[i][0]=0;else if(p[i]<0)f11[i][0]=f21[i][0]=p[i];else f12[i][0]=f22[i][0]=p[i];}
for(int i=1;i<=18;i++){
for(int j=1;j<=n-(1<<i)+1;j++){
f11[j][i]=max(f11[j][i-1],f11[j+(1<<i-1)][i-1]);
f12[j][i]=max(f12[j][i-1],f12[j+(1<<i-1)][i-1]);
f21[j][i]=min(f21[j][i-1],f21[j+(1<<i-1)][i-1]);
f22[j][i]=min(f22[j][i-1],f22[j+(1<<i-1)][i-1]);
}
}
}
int gmin1(int l,int r){
int k=lg2[r-l+1];
return min(f21[l][k],f21[r-(1<<k)+1][k]);
}
int gmin2(int l,int r){
int k=lg2[r-l+1];
return min(f22[l][k],f22[r-(1<<k)+1][k]);
}
int gmax1(int l,int r){
int k=lg2[r-l+1];
return max(f11[l][k],f11[r-(1<<k)+1][k]);
}
int gmax2(int l,int r){
int k=lg2[r-l+1];
return max(f12[l][k],f12[r-(1<<k)+1][k]);
}
int gmin(int l,int r){
return min(gmin1(l,r),gmin2(l,r));
}
int gmax(int l,int r){
return max(gmax1(l,r),gmax2(l,r));
}
}q1,q2;
signed main(){
freopen("game15.in","r",stdin);
freopen("game15.out","w",stdout);
for(int i=1;i<=100000;i++)lg2[i]=log2(i);
cin>>n>>m>>asks;
for(int i=1;i<=n;i++)scanf("%lld",&a[i]),q1.p[i]=a[i];
for(int i=1;i<=m;i++)scanf("%lld",&b[i]),q2.p[i]=b[i];
q1.init();q2.init();
while(asks--){
int l1,r1,l2,r2;
scanf("%lld%lld%lld%lld",&l1,&r1,&l2,&r2);
int am=q1.gmax(l1,r1),an=q1.gmin(l1,r1),bm=q2.gmax(l2,r2),bn=q2.gmin(l2,r2);
if(bn>=0){
if(an>=0)printf("%lld\n",q1.gmax(l1,r1)*q2.gmin(l2,r2));
else if(am<=0)printf("%lld\n",q1.gmax(l1,r1)*q2.gmax(l2,r2));
else{
printf("%lld\n",q1.gmax(l1,r1)*q2.gmin(l2,r2));
}
}else if(bm>=0&&bn<=0){
if(an>=0){
printf("%lld\n",q1.gmin(l1,r1)*q2.gmin(l2,r2));
}else if(am<=0){
printf("%lld\n",q1.gmax(l1,r1)*q2.gmax(l2,r2));
}else{
printf("%lld\n",max(q1.gmin2(l1,r1)*q2.gmin1(l2,r2),q1.gmax1(l1,r1)*q2.gmax2(l2,r2)));
}
}else{
if(an>=0)printf("%lld\n",q1.gmin(l1,r1)*q2.gmin(l2,r2));
else printf("%lld\n",q1.gmin(l1,r1)*q2.gmax(l2,r2));
}
}
return 0;
}