题目
在一个平面直角坐标系上有\(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)\)。
可能会出的锅是会出现不合法的情况，就是它们实际上的位置关系并不满足右上左下的偏序关系。
麻烦的做法是：求出对于每个右上端点的合法的左下端点的区间。求出\(p\)之后，将序列分成三个部分：区间包含\(p\)的，区间在\(p\)左边的，区间在\(p\)右边的，然后继续做。实现比较复杂，反正我没有成功。时间复杂度应该是\(O(n\lg n)\)的。
简单的做法是：不合法的情况只需要考虑，右上变左下，左下变右上的情况。发现如果出现这种情况，那么两个序列各自分成两段，两边变成子问题继续做下去是没有问题的。因为如果出现了如此的\(mid\)和\(i\)（\(i\)贡献不要求最大），那么\((mid,R]\)和\([l,i)\)不会互相影响。时间复杂度也是\(O(n\lg n)\).
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;
}