bzoj 4951: [Wf2017]Money for Nothing

.

题意：给出n个生产者的开始生产时间和成本，和m个消费者的收购价格和收购截至时间，只能指定一个生产者和一个消费者，每天可以倒卖1个零件，问最大收益。
题解：分治
先把这题转换成一个几何问题：给出n个矩形的左下角和m个矩形的右上角，求最大矩形。设左下角点集为$L$，右上角为$U$再预处理一下，把那些不可能成为答案的点去掉，最终使得$L_i.x\lt L_{i+1}.x$且$L_i.y\gt L_{i+1}.y$。$U$也一样，只是去掉的点不同。具体看代码。然后设$u(i)$表示以$L_i$为左下角的最大矩形的右上角的编号。$u(i)$是递增的，这里证明一下吧：
如图：$u(A)=B$，所以$S_{OTUB}\gt S_{CMNO}$，假如$u(D)=C$那么就要满足$S_{CQPO}\gt S_{SBOR}$，这显然是不成立的。
所以，我们就可以分治来搞：每次我们处理左下角在$l_1\sim r_1$之间，右上角在$l_2\sim r_2$之间的最大值，设$md=(l1+r1)/2$，递归下去找$l_1\sim md l_2\sim u(md)$和$md\sim r_1 u(md)\sim r_2$。这样总共$logn$层，每层总共遍历一次$U$，再加上预处理排序的$nlogn$，总复杂度就是$O((n+m)logn)$
代码：

#include<bits/stdc++.h>
using namespace std;

int n,m;
struct pnt
{
    int x,y;
}a[500010],b[500010];

int cmp(pnt x,pnt y)
{
    return x.x==y.x?x.y<y.y:x.x<y.x;
}
int pre(pnt*a,int size,int type)
{
    sort(a,a+size,cmp);
    static bool del[500010];
    memset(del,0,sizeof(del));
    if(type==0)
    {
        int last=0;
        for(int i=1;i<size;i++)
        {
            if(a[i].y>=a[last].y)
            del[i]=1;
            else
            last=i;
        }
    }
    else
    {
        int last=size-1;
        for(int i=size-2;i>=0;i--)
        {
            if(a[i].y<=a[last].y)
            del[i]=1;
            else
            last=i;
        }
    }
    int nn=0;
    for(int i=0;i<size;i++)
    if(!del[i])
    a[nn++]=a[i];
    return nn;
}
long long get(int x,int y)
{
    if(b[y].x<a[x].x&&b[y].y<a[x].y)
    return 0;
    return (long long)(b[y].x-a[x].x)*(b[y].y-a[x].y);
}
long long wk(int l1,int r1,int l2,int r2)
{
    if(l1==r1)
    return 0;
    int md=l1+r1>>1,hh=l2;
    for(int i=l2+1;i<r2;i++)
    if(get(md,hh)<get(md,i))
    hh=i;
    return max(max(wk(l1,md,l2,hh+1),wk(md+1,r1,hh,r2)),get(md,hh));
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)
    {
        scanf("%d%d",&a[i].x,&a[i].y);
    }
    for(int i=0;i<m;i++)
    {
        scanf("%d%d",&b[i].x,&b[i].y);
    }
    n=pre(a,n,0);
    m=pre(b,m,1);/*
    puts("");
    for(int i=0;i<n;i++)
    printf("%d %d\n",a[i].x,a[i].y);
    puts("");
    for(int i=0;i<m;i++)
    printf("%d %d\n",b[i].x,b[i].y);
    for(int i=0;i<n;i++)
    {
        int hh=0;
        for(int j=0;j<m;j++)
        if(get(i,hh)<get(i,j))
        hh=j;
        printf("%d %d\n",i,hh);
    }*/
    printf("%lld",wk(0,n,0,m));
}