A Gym-101471D Money for nothing
就是求 \((d_j-c_i)(q_j-p_i)\) 的最大值。
可以看作点对 \((d_j,q_j)\) 与 \((c_i,p_i)\) 在二维平面上构成矩形的最大值，且 \(c_i\ge d_j,p_i\ge q_j\)。
把卖家点对放在序列 \(a\)，买家点对放在序列 \(b\)，先删去一定不优的点，删完之后 \(a,b\) 都是单调递减的。
画图发现如果 \(b_2\) 在 \(a_1\) 处优于 \(b_1\)，那么也一定在 \(a_2\) 处优于 \(b_1\)，这样就有决策单调性了，分治即可。
点击查看代码
int m,n;
pii a[maxn],b[maxn];
int tota,totb;
ll ans=-llinf;
void solve(int l1,int r1,int l2,int r2){
if(l1>r1) return;
ll mx=-llinf;
if(l1==r1){
for(int i=l2;i<=r2;++i){
if(b[i].fir>=a[l1].fir&&b[i].sec>=a[l1].sec){
mx=max(mx,1ll*(b[i].fir-a[l1].fir)*(b[i].sec-a[l1].sec));
}
}
ans=max(ans,mx);
return;
}
int mid=(l1+r1)>>1,x=0;
if(b[l2].sec<=a[mid].sec) return solve(mid+1,r1,l2,r2);
for(int i=l2;i<=r2&&b[i].sec>a[mid].sec;++i){
if(1ll*(b[i].fir-a[mid].fir)*(b[i].sec-a[mid].sec)>=mx){
mx=1ll*(b[i].fir-a[mid].fir)*(b[i].sec-a[mid].sec),x=i;
}
}
ans=max(ans,mx);
solve(l1,mid-1,l2,x),solve(mid+1,r1,x,r2);
}
int main(){
m=read(),n=read();
for(int i=1;i<=m;++i) a[i].sec=read(),a[i].fir=read();
for(int i=1;i<=n;++i) b[i].sec=read(),b[i].fir=read();
sort(a+1,a+m+1,[&](pii &X,pii &Y){
if(X.fir==Y.fir) return X.sec<Y.sec;
else return X.fir<Y.fir;
});
sort(b+1,b+n+1,[&](pii &X,pii &Y){
if(X.fir==Y.fir) return X.sec>Y.sec;
else return X.fir>Y.fir;
});
int mx=-inf,mn=inf;
for(int i=1;i<=m;++i){
if(mn<a[i].sec) continue;
a[++tota]=a[i];
mn=a[i].sec;
}
for(int i=1;i<=n;++i){
if(mx>b[i].sec) continue;
b[++totb]=b[i];
mx=b[i].sec;
}
m=tota,n=totb;
sort(b+1,b+n+1,[&](pii &X,pii &Y){
return X.fir<Y.fir;
});
solve(1,m,1,n);
ans=max(ans,0ll);
printf("%lld\n",ans);
return 0;
}