先附上我的代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int n,m,q;
int a[N],b[N];
struct Node{
struct node{
int maxi,mini,nmax,pmin;
}tree[N<<2];
void pushup(int cur){
tree[cur].maxi=max(tree[cur<<1].maxi,tree[cur<<1|1].maxi);
tree[cur].mini=min(tree[cur<<1].mini,tree[cur<<1|1].mini);
tree[cur].nmax=max(tree[cur<<1].nmax,tree[cur<<1|1].nmax);
tree[cur].pmin=min(tree[cur<<1].pmin,tree[cur<<1|1].pmin);
}
void build(int cur,int lt,int rt,int t[]){
if(lt==rt){
tree[cur].maxi=tree[cur].mini=t[lt];
tree[cur].nmax=-(int)4e9;
tree[cur].pmin=(int)4e9;
if(t[lt]<=0) tree[cur].nmax=t[lt];
if(t[lt]>=0) tree[cur].pmin=t[lt];
return;
}
int mid=(lt+rt)>>1;
build(cur<<1,lt,mid,t);
build(cur<<1|1,mid+1,rt,t);
pushup(cur);
}
int query_min(int cur,int lt,int rt,int qx,int qy){
if(lt>qy||rt<qx) return (int)4e9;
if(lt>=qx&&rt<=qy) return tree[cur].mini;
int mid=(lt+rt)>>1;
return min(query_min(cur<<1,lt,mid,qx,qy),query_min(cur<<1|1,mid+1,rt,qx,qy));
}
int query_max(int cur,int lt,int rt,int qx,int qy){
if(lt>qy||rt<qx) return -(int)4e9;
if(lt>=qx&&rt<=qy) return tree[cur].maxi;
int mid=(lt+rt)>>1;
return max(query_max(cur<<1,lt,mid,qx,qy),query_max(cur<<1|1,mid+1,rt,qx,qy));
}
int query_pmin(int cur,int lt,int rt,int qx,int qy){
if(lt>qy||rt<qx) return (int)4e9;
if(lt>=qx&&rt<=qy) return tree[cur].pmin;
int mid=(lt+rt)>>1;
return min(query_pmin(cur<<1,lt,mid,qx,qy),query_pmin(cur<<1|1,mid+1,rt,qx,qy));
}
int query_nmax(int cur,int lt,int rt,int qx,int qy){
if(lt>qy||rt<qx) return -(int)4e9;
if(lt>=qx&&rt<=qy) return tree[cur].nmax;
int mid=(lt+rt)>>1;
return max(query_nmax(cur<<1,lt,mid,qx,qy),query_nmax(cur<<1|1,mid+1,rt,qx,qy));
}
}A,B;
signed main(){
ios::sync_with_stdio(false);
cin>>n>>m>>q;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=m;i++) cin>>b[i];
A.build(1,1,n,a);
B.build(1,1,m,b);
while(q--){
int la,ra,lb,rb;
cin>>la>>ra>>lb>>rb;
int maxa=A.query_max(1,1,n,la,ra),mina=A.query_min(1,1,n,la,ra);
int maxb=B.query_max(1,1,m,lb,rb),minb=B.query_min(1,1,m,lb,rb);
int pmina=A.query_pmin(1,1,n,la,ra),nmaxa=A.query_nmax(1,1,n,la,ra);
// int pminb=B.query_pmin(1,1,m,lb,rb),nmaxb=B.query_nmax(1,1,m,lb,rb);
// cout<<pmina<<" "<<nmaxa<<": "<<pminb<<" "<<nmaxb<<"\n";
if(maxa>0&&minb>0) cout<<maxa*minb<<"\n";
else if(maxa<0&&minb>0) cout<<maxa*maxb<<"\n";
else if(mina>0&&minb<0) cout<<mina*minb<<"\n";
else if(mina<0&&minb<0&&maxb<0) cout<<mina*maxb<<"\n";
else cout<<max(pmina*minb,nmaxa*maxb)<<"\n";
}
return 0;
}
/*
A>0,B>0
L选择A[l,r]中最大的一个
Q选择B[l,r]中最小的一个
A>0,B<0
L选择A[l,r]中最小的一个
Q选择B[l,r]中最小的一个
A<0,B>0
L选择A[l,r]中最大的一个
Q选择B[l,r]中最小的一个
A<0,B<0
B全部<0
L选择A[l,r]中最小的一个
Q选择B[l,r]中最大的一个
B部分<0
如果B负数最大值的绝对值小于其正数最小值的绝对值,那么L选A[l,r]中的正数最小值
反之就是负数最大值。
*/
/*
-2 2 3
-1 1
*/
/*
特殊性质2的点挂了3/4?iee
*/
首先是对线段树一类边界的取值问题
比如当我代码中的边界取 ±1e9 时就只有 85pts 评测记录。
但如果把边界取到 ±4e9 的时候就可以过掉 CCF 数据了。
再开大点到 1e18 时又只有 20pts 了。
想知道为什么边界会对答案有如此大的影响,按照个人理解只要边界的绝对值大于 1e9 就行了。还是说是代码中分类讨论不够彻底而导致有边界进入到了答案运算中。
其次是民间数据导致的 Unaccepted 100 问题
在我的边界改到 4e9 后民间数据第三个点过不掉 评测记录。想知道怎么改,可怜的孩子已经卡了一晚上了/kk。
谢谢您能看完这个求助帖!