@[AllureLove2410](/user/556455) 每个人只会从最大的负数、最小的负数、最大的正数、最小的正数和零中选,证明显然(绝对不是我懒)
by yizhiming @ 2022-11-03 13:40:57
@[yizhiming](/user/369399) 我知道,就是想问下怎么选
by AllureLove2410 @ 2022-11-03 13:42:01
至于具体他怎么选。。。为什么不直接枚举捏
by yizhiming @ 2022-11-03 13:42:25
@[yizhiming](/user/369399) 因为我按照这样写了只有65pts,就是只拿了全部的特殊性质分
by AllureLove2410 @ 2022-11-03 13:42:45
@[yizhiming](/user/369399) 行吧行吧,还是谢谢您
by AllureLove2410 @ 2022-11-03 13:44:02
对于第一个人,直接枚举他选哪个,另一个人选哪个,从中选最小值最大的
因为第一个人选什么,第二个人都会根据他的选择最小的,所以只要枚举求出第一个人选 x 时,所能求出的最小值记作 $min_x$ ,求所有 $min_x$ 的最大值
by yizhiming @ 2022-11-03 13:44:36
要不我看看代码?
by yizhiming @ 2022-11-03 13:44:55
@[yizhiming](/user/369399) 我的想法有点不一样,我是从最大值,最小值,绝对值最小,这三个去选,求hack
by AllureLove2410 @ 2022-11-03 13:47:28
@[yizhiming](/user/369399)
代码:
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int xrt=1e5+3;
int n,m,q;
int a[xrt],b[xrt];
struct zsm{
int l,r;
int mins,maxs;
int minsabs;//感觉好浪费
bool flag;
};
bool fc;
zsm ta[xrt<<2],tb[xrt<<2];
void builda(int x,int l,int r){
ta[x].l=l,ta[x].r=r;
if(l==r){
ta[x].maxs=a[l];
ta[x].mins=a[l];
ta[x].minsabs=abs(a[l]);
if(a[l]<0)ta[x].flag=true;
return;
}
int mid=l+((r-l)>>1);
builda(x<<1,l,mid);
builda(x<<1|1,mid+1,r);
ta[x].maxs=max(ta[x<<1].maxs,ta[x<<1|1].maxs);
ta[x].mins=min(ta[x<<1].mins,ta[x<<1|1].mins);
if(ta[x<<1].minsabs<ta[x<<1|1].minsabs){
ta[x].minsabs=ta[x<<1].minsabs;
ta[x].flag=ta[x<<1].flag;
}else{
ta[x].minsabs=ta[x<<1|1].minsabs;
ta[x].flag=ta[x<<1|1].flag;
}
// ta[x].minsabs=min(ta[x<<1].minsabs,ta[x<<1|1].minsabs);
return;
}
void buildb(int x,int l,int r){
tb[x].l=l,tb[x].r=r;
if(l==r){
tb[x].maxs=b[l];
tb[x].mins=b[l];
tb[x].minsabs=abs(b[l]);
return;
}
int mid=l+((r-l)>>1);
buildb(x<<1,l,mid);
buildb(x<<1|1,mid+1,r);
tb[x].maxs=max(tb[x<<1].maxs,tb[x<<1|1].maxs);
tb[x].mins=min(tb[x<<1].mins,tb[x<<1|1].mins);
return;
}
int minab(int x,int l,int r){//这里出问题了
if(ta[x].l>=l&&ta[x].r<=r){
int ans=1;
ans-=ta[x].flag*2;
return ta[x].minsabs*ans;
}
int mid=ta[x].l+((ta[x].r-ta[x].l)>>1);
int ans=1e18;
if(l<=mid){
int k=minab(x<<1,l,r);
if(k<abs(ans)){
ans=k;
}
if(k==abs(ans)&&k==0-ans){
fc = true;
}else fc=false;
}
if(r>mid){
int k=minab(x<<1|1,l,r);
if(k<abs(ans)){
ans=k;
}
if(k==abs(ans)&&k==0-ans){
fc = true;
}else fc = false;
}
return ans;
}
int mina,minb,minabs,maxa,maxb;
int fmina(int x,int l,int r){
if(ta[x].l>=l&&ta[x].r<=r){
return ta[x].mins;
}
int mid=ta[x].l+((ta[x].r-ta[x].l)>>1);
int ans=1e18;
if(l<=mid){
ans=min(ans,fmina(x<<1,l,r));
}
if(r>mid){
ans=min(ans,fmina(x<<1|1,l,r));
}
return ans;
}
int fminb(int x,int l,int r){
if(tb[x].l>=l&&tb[x].r<=r){
return tb[x].mins;
}
int mid=tb[x].l+((tb[x].r-tb[x].l)>>1);
int ans=1e18;
if(l<=mid){
ans=min(ans,fminb(x<<1,l,r));
}
if(r>mid){
ans=min(ans,fminb(x<<1|1,l,r));
}
return ans;
}
int fmaxa(int x,int l,int r){
if(ta[x].l>=l&&ta[x].r<=r){
return ta[x].maxs;
}
int mid=ta[x].l+((ta[x].r-ta[x].l)>>1);
int ans=-1e18;
if(l<=mid){
ans=max(ans,fmaxa(x<<1,l,r));
}
if(r>mid){
ans=max(ans,fmaxa(x<<1|1,l,r));
}
return ans;
}
int fmaxb(int x,int l,int r){
if(tb[x].l>=l&&tb[x].r<=r){
return tb[x].maxs;
}
int mid=tb[x].l+((tb[x].r-tb[x].l)>>1);
int ans=-1e18;
if(l<=mid){
ans=max(ans,fmaxb(x<<1,l,r));
}
if(r>mid){
ans=max(ans,fmaxb(x<<1|1,l,r));
}
return ans;
}
int la,ra,lb,rb;
void work(){
fc=false;
mina=fmina(1,la,ra);
minb=fminb(1,lb,rb);
minabs=minab(1,la,ra);
maxa=fmaxa(1,la,ra);
maxb=fmaxb(1,lb,rb);
return;
}
int ua,ub;
void check(){
cout<<"\na:\n";
cout<<mina<<" "<<maxa<<" "<<minabs<<"\n";
cout<<"b:\n";cout<<minb<<" "<<maxb<<"\n";
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
//freopen("game.in","r",stdin);
//freopen("game.out","w",stdout);
cin>>n>>m>>q;
for(int i=1;i<=n;i++){
cin>>a[i];
}
builda(1,1,n);
for(int i=1;i<=m;i++){
cin>>b[i];
}
buildb(1,1,m);
for(int i=1;i<=q;i++){
cin>>la>>ra>>lb>>rb;
work();
//check();
if(minb<0&&maxb>0){
// if(fc==false){
ua=minabs;
// }
}else if(minb>0){
ua=maxa;
}else ua=mina;
if(mina<0&&maxa>0){
if(ua>0){
ub=minb;
}else ub=maxb;
}else if(maxa<0){
ub=maxb;
}else ub=minb;
int qwe=ua*ub;
if(fc==true){
if(minb<0&&maxb>0){
// if(fc==false){
ua=minabs;
// }
}else if(minb>0){
ua=maxa;
}else ua=mina;
if(mina<0&&maxa>0){
if(ua>0){
ub=minb;
}else ub=maxb;
}else if(maxa<0){
ub=maxb;
}else ub=minb;
}
cout<<max(ua*ub,qwe)<<"\n";
}
return 0;
```
by AllureLove2410 @ 2022-11-03 13:47:55
然后我特判了两个绝对值相同但一正一负的情况
by AllureLove2410 @ 2022-11-03 13:49:06