你的INT_MAX可能不太够,试试1e18,~~我就是这错了得了40pts~~
by cmrhhh @ 2024-03-10 15:17:54
我的代码:
```cpp
#include<bits/stdc++.h>
using namespace std;//方便起见,0当正数
#define int long long
const int maxn=1e5+10,inf=1e18+10;//inf开大点
int n,m,q,a[maxn],b[maxn],l1,l2,r1,r2;
int lg[maxn],st_a_min_P[maxn][33],st_a_min_N[maxn][33],st_a_max_P[maxn][33],st_a_max_N[maxn][33],
st_b_min_P[maxn][33],st_b_max_P[maxn][33],st_b_min_N[maxn][33],st_b_max_N[maxn][33];
int ans;
void a_build(){
for(int j=1;j<=31;j++){
for(int i=1;i+(1<<j-1)<=n;i++){
st_a_max_P[i][j]=max(st_a_max_P[i][j-1],st_a_max_P[i+(1<<j-1)][j-1]);
st_a_min_P[i][j]=min(st_a_min_P[i][j-1],st_a_min_P[i+(1<<j-1)][j-1]);
st_a_max_N[i][j]=max(st_a_max_N[i][j-1],st_a_max_N[i+(1<<j-1)][j-1]);
st_a_min_N[i][j]=min(st_a_min_N[i][j-1],st_a_min_N[i+(1<<j-1)][j-1]);
}
}
}
void b_build(){
for(int j=1;j<=31;j++){
for(int i=1;i+(1<<j-1)<=m;i++){
st_b_max_P[i][j]=max(st_b_max_P[i][j-1],st_b_max_P[i+(1<<j-1)][j-1]);
st_b_min_P[i][j]=min(st_b_min_P[i][j-1],st_b_min_P[i+(1<<j-1)][j-1]);
st_b_max_N[i][j]=max(st_b_max_N[i][j-1],st_b_max_N[i+(1<<j-1)][j-1]);
st_b_min_N[i][j]=min(st_b_min_N[i][j-1],st_b_min_N[i+(1<<j-1)][j-1]);
}
}
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m>>q;
for(int i=2;i<=maxn;i++)lg[i]=lg[i/2]+1;
for(int i=1;i<=n;++i){
cin>>a[i];
if(a[i]<=0){
st_a_min_N[i][0]=a[i];
st_a_max_N[i][0]=a[i];
st_a_min_P[i][0]=inf;
st_a_max_P[i][0]=-inf;
}
if(a[i]>0){
st_a_min_N[i][0]=inf;
st_a_max_N[i][0]=-inf;
st_a_min_P[i][0]=a[i];
st_a_max_P[i][0]=a[i];
}
}
for(int i=1;i<=m;++i){
cin>>b[i];
if(b[i]<=0){
st_b_min_N[i][0]=b[i];
st_b_max_N[i][0]=b[i];
st_b_min_P[i][0]=inf;
st_b_max_P[i][0]=-inf;
}
if(b[i]>0){
st_b_min_N[i][0]=inf;
st_b_max_N[i][0]=-inf;
st_b_min_P[i][0]=b[i];
st_b_max_P[i][0]=b[i];
}
}
a_build();
b_build();
while(q--){
ans=-inf;
cin>>l1>>r1>>l2>>r2;
int x1=r1-l1+1,x2=r2-l2+1;
int a_max_P=max(st_a_max_P[l1][lg[x1]],st_a_max_P[r1-(1<<lg[x1])+1][lg[x1]]);
int a_min_P=min(st_a_min_P[l1][lg[x1]],st_a_min_P[r1-(1<<lg[x1])+1][lg[x1]]);
int b_max_P=max(st_b_max_P[l2][lg[x2]],st_b_max_P[r2-(1<<lg[x2])+1][lg[x2]]);
int b_min_P=min(st_b_min_P[l2][lg[x2]],st_b_min_P[r2-(1<<lg[x2])+1][lg[x2]]);
int a_max_N=max(st_a_max_N[l1][lg[x1]],st_a_max_N[r1-(1<<lg[x1])+1][lg[x1]]);
int a_min_N=min(st_a_min_N[l1][lg[x1]],st_a_min_N[r1-(1<<lg[x1])+1][lg[x1]]);
int b_max_N=max(st_b_max_N[l2][lg[x2]],st_b_max_N[r2-(1<<lg[x2])+1][lg[x2]]);
int b_min_N=min(st_b_min_N[l2][lg[x2]],st_b_min_N[r2-(1<<lg[x2])+1][lg[x2]]);
if(a_max_P!=-inf){
if(b_min_P!=inf&&b_min_N!=inf)ans=max(ans,min(a_max_P*b_min_P,a_max_P*b_min_N));
else if(b_min_P!=inf)ans=max(ans,a_max_P*b_min_P);
else if(b_min_N!=inf)ans=max(ans,a_max_P*b_min_N);
}
if(a_min_P!=inf){
if(b_min_P!=inf&&b_min_N!=inf)ans=max(ans,min(a_min_P*b_min_P,a_min_P*b_min_N));
else if(b_min_P!=inf)ans=max(ans,a_min_P*b_min_P);
else if(b_min_N!=inf)ans=max(ans,a_min_P*b_min_N);
}
if(a_max_N!=-inf){
if(b_max_N!=-inf&&b_max_P!=-inf)ans=max(ans,min(a_max_N*b_max_P,a_max_N*b_min_N));
else if(b_max_N!=-inf)ans=max(ans,a_max_N*b_max_N);
else if(b_max_P!=-inf)ans=max(ans,a_max_N*b_max_P);
}
if(a_min_N!=inf){
if(b_max_P!=-inf&&b_max_N!=-inf)ans=max(ans,min(a_min_N*b_max_P,a_min_N*b_max_N));
else if(b_max_P!=-inf)ans=max(ans,a_min_N*b_max_P);
else if(b_max_N!=-inf)ans=max(ans,a_min_N*b_max_N);
}
cout<<ans<<"\n";
}
return 0;
}
/*
6 4 1
3 -1 -2 1 2 0
1 2 -1 -3
2 6 3 4
*/
```
by cmrhhh @ 2024-03-10 15:18:44
已AC,此帖结
by _6_awa @ 2024-03-10 20:08:06