bzoj 2369

首先，最优解一定可以通过选两个线段达到。也就是说当选了多个线段的时候，只要选最左边那个和最右边那个就可以达到一样的效果

其次，假如一个线段被另一个线段所包含，那么包括他的可能成为最优解的只有他和包括他的最长的线段这一对。

最后，对于所有线段按左端点排序，所有线段的左端点和右端点一定都是递增的。设$f(x, y)$为选$x, y$得到的收益，对于$i<j<k<k’$，若有$$f(i, k)<f(j, k)$$则一定有$$f(i, k’)<f(j, k’)$$

证明如下

$$\begin{split}
f(i, k)&<f(j, k)\\
(r_k-l_i)\cdot (r_i-l_k)&<(r_{k}-l_j)\cdot (r_{j}-l_{k})\\
r_{k}r_{i}-l_ir_i-l_kr_k+l_il_k&<r_kr_j-l_jr_j-l_kr_k+l_jl_k\\
r_{k}(r_{i}-r_j)+l_k(l_i-l_j)&<l_ir_i-l_jr_j\\
\end{split}$$

另外这里这种递归做法据说可以卡掉（时间复杂度），但是挺难卡的，如果要保证不被卡请写单调队列

#include <iostream>
#include <cstdio>
#include <algorithm>

typedef long long ll;

struct Data{
    int l, r;
}a[1000010], b[1000010];

int N, top;
ll ans;

bool cmp(Data x, Data y){
    return x.l==y.l ? x.r>y.r : x.l<y.l;
}

void divide(int l, int r, int ql, int qr){
    if(l>r) return;
    int mid=(l+r)>>1, p=-1;
    ll mx=0;
    for(int i=std::min(qr, mid-1); i>=ql && b[i].r>b[mid].l; i--){
        ll t=1ll*(b[i].r-b[mid].l)*(b[mid].r-b[i].l);
        if(t>mx) mx=t, p=i;
    }
    ans=std::max(ans, mx);
    if(~p){
        divide(l, mid-1, ql, p);
        divide(mid+1, r, p, qr);
    }else{
        divide(l, mid-1, ql, qr);
        divide(mid+1, r, ql, qr);
    }
}

int main(){
    scanf("%d", &N);
    for(int i=1; i<=N; i++)
        scanf("%d%d", &a[i].l, &a[i].r);
    std::sort(a+1, a+N+1, cmp);
    int mx=a[1].r, p=1;
    b[++top]=a[1];
    for(int i=2; i<=N; i++)
        if(a[i].r>mx)
            mx=a[i].r, b[++top]=a[i], p=i;
        else
            ans=std::max(ans, 1ll*(a[i].r-a[i].l)*(a[p].r-a[p].l));
    divide(2, top, 1, top);
    printf("%lld\n", ans);
    return 0;
}