2017 ACM-ICPC World Finals D Money for Nothing

題目

在一個平面直角坐标系上有\(n\)個矩形的左下端點和\(m\)個矩形的右上端點。

找到一個左下端點和一個右上端點，使得形成的矩形面積最大。

\(n,m\le 5*10^5\)

似曾相識。

首先将一些顯然不會最優的點去掉，那麼就會得到兩個點的序列，都是從左上到右下排布。

考慮對于一個右上端點\(a\)，假如有左下端點\(p\)比左下端點\(q\)優：

\((x_a-x_p)(y_a-y_p)\ge (x_a-x_q)(y_a-y_q)\)

整理得\((x_px_q-y_py_q)-x_a(y_p-y_q)-y_a(x_p-x_q)>0\)

如果\(p<q\)，那麼\(y_p-y_q>0,x_p-x_q<0\)，是以當\(x_a\)減小或\(y_a\)增大時，這條式子仍然成立。此時如果有\(b<a\)，那麼對于\(b\)來說，選擇\(p\)比選擇\(q\)優。

如果\(p>q\)，類似地考慮。

于是就可以發現決策單調性。

直接按順序DP是不行的，因為如果要找到決策點，那麼要從上一個位置的決策點找到序列末尾。

是以可以分治地做：設\((L,R,l,r)\)表示處理右上端點\([L,R]\)區間，左下端點\([l,r]\)區間。每次取\([L,R]\)中點\(mid\)，找到它的最優決策點\(p\)，然後分成兩個子問題\((L,mid-1,l,p)\)和\((mid+1,R,p,r)\)。

using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cassert>
#define N 500010
#define ll long long
#define INF 2000000000
int n,m;
struct DOT{
	int x,y;
} a[N],b[N];
bool cmpd(DOT a,DOT b){return a.x<b.x || a.x==b.x && a.y<b.y;}
void init(DOT a[],int &n,int f){
	if (f==-1)
		for (int i=1;i<=n;++i)
			a[i].x*=-1,a[i].y*=-1;
	sort(a+1,a+n+1,cmpd);
	int t=0;
	int y=INF;
	for (int i=1;i<=n;++i)
		if (i==1 || a[i].y<y)
			a[++t]=a[i],y=a[i].y;
	n=t;
	if (f==-1){
		for (int i=1;i<=n;++i)
			a[i].x*=-1,a[i].y*=-1;
		reverse(a+1,a+n+1);
	}
}
int L[N],R[N],pl[N],pr[N];
ll ans;
ll calc(int i,int p){
	return (ll)(b[i].x-a[p].x)*(b[i].y-a[p].y);
}
void divide(int bl,int br,int al,int ar){
	if (bl>br || al>ar) return;
	int mid=bl+br>>1;
	int p=-1;
	for (int i=al;i<=ar;++i){
		if (b[mid].x<=a[i].x && b[mid].y<=a[i].y){
			divide(bl,mid-1,al,i-1);
			divide(mid+1,br,i+1,ar);
			return;
		}
		if (p==-1 || calc(mid,p)<calc(mid,i))
			p=i;
	}
	if (p!=-1)
		ans=max(ans,calc(mid,p));
	divide(bl,mid-1,al,p);
	divide(mid+1,br,p,ar);
}
int main(){
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;++i)
		scanf("%d%d",&a[i].x,&a[i].y);
	for (int i=1;i<=m;++i)
		scanf("%d%d",&b[i].x,&b[i].y);
	init(a,n,1);
	init(b,m,-1);
	for (int i=1;i<n;++i)
		assert(a[i].x<a[i+1].x && a[i].y>a[i+1].y);
	for (int i=1;i<m;++i)
		assert(b[i].x<b[i+1].x && b[i].y>b[i+1].y);
	divide(1,m,1,n);
	printf("%lld\n",ans);
	return 0;
}