题目概述

有 $n$ 个区间 $A_i=[L_i,R_i]$ ，现在选 $m$ 个 $(m>1)$ 区间，贡献为 $|A_{k_1}\cap A_{k_2}\cap A_{k_3}\cdots A_{k_m}|\times|A_{k_1}\cup A_{k_2}\cup A_{k_3}\cdots A_{k_m}|$ ，求最大贡献。

解题报告

显然最大贡献是只选两个区间，所以我们先把区间排序，去掉被包含的区间（注意去重时也需要计算贡献），然后就可以定义 $f_i=max\{(R_j-L_i)(R_i-L_j)|j<i\}$ 表示 $i$ 的最大贡献。

决策单调性是什么呢？和斜率优化类似，如果 $j$ 对于 $k$ 比 $i$ 好能够推出对于 $t(t>k)$ $j$ 也比 $i$ 好，就说明决策点是单调的，这样就可以减少很多没有必要的枚举。

对于这题，令 $i<j<k<t$ ，假设 $j$ 比 $i$ 好，那么：

$$ (R_k-L_j)(R_j-L_k)>(R_k-L_i)(R_i-L_k)\\ R_jR_k-R_kL_k-R_jL_j+L_jL_k>R_iR_k-R_kL_k-R_iL_i+L_iL_k\\ R_k(R_j-R_i)+L_k(L_j-L_i)>R_jL_j-R_iL_i\\ ∵ L_t>L_k,R_t>R_k\\ R_t(R_j-R_i)+L_t(L_j-L_i)>R_jL_j-R_iL_i\\ (R_t-L_j)(R_j-L_t)>(R_t-L_i)(R_i-L_t)\\ $$

所以满足决策单调性，我们就可以分治了！$Solve(L,R,l,r)$ 表示求出 $f_{[L,R]}$ ，决策点范围在 $[l,r]$ 。那么我们可以先求出 $f_{mid}$ 的决策点 $pos$ ，然后 $Solve(L,mid,l,pos),Solve(mid+1,R,pos,r)$ 就行了。

注意决策单调性并不一定都能够用分治，因为很明显 $f$ 在 $Solve$ 之前是未知的，所以如果 $f$ 的转移方程中包含 $f$ 就不能够用分治了。

示例程序

#include<cstdio>
#include<cctype>
#include<algorithm>
#define fr first
#define sc second
using namespace std;
typedef long long LL;
const int maxn=1000000;

int n;LL ans;pair<int,int> s[maxn+5];bool vis[maxn+5];

#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    if (l==r) r=(l=buf)+fread(buf,1,100000,stdin);
    if (l==r) return EOF;return *l++;
}
inline int readi(int &x){
    int tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+ch-48,ch=readc();
    return lst=='-'?x=-tot:x=tot,Eoln(ch);
}
inline bool cmp(pair<int,int> a,pair<int,int> b) {return a.fr<b.fr||a.fr==b.fr&&a.sc>b.sc;}
#define val(i,j) ((LL)(s[j].sc-s[i].fr)*(s[i].sc-s[j].fr))
LL Solve(int L,int R,int l,int r){
    if (L==R) {LL MAX=0;for (int i=l;i<=r&&i<L;i++) MAX=max(MAX,val(i,L));return MAX;}
    int mid=L+(R-L>>1);LL MAX=0;int pos=mid;
    for (int i=l;i<=r&&i<mid;i++) if (val(i,mid)>MAX) MAX=val(i,mid),pos=i;
    return max(MAX,max(Solve(L,mid,l,pos),Solve(mid+1,R,pos,r)));
}
int main(){
    freopen("program.in","r",stdin);
    freopen("program.out","w",stdout);
    readi(n);for (int i=1;i<=n;i++) readi(s[i].fr),readi(s[i].sc);sort(s+1,s+1+n);
    for (int i=1,j;i<=n;i=j)
        for (j=i+1;j<=n;vis[j++]=true){
            if (s[j].sc>s[i].sc) break;
            ans=max(ans,(LL)(s[i].sc-s[i].fr)*(s[j].sc-s[j].fr));
        }
    for (int tot=n,i=(n=0,1);i<=tot;i++) if (!vis[i]) s[++n]=s[i];
    if (n==1) return printf("%lld\n",ans),0;
    return printf("%lld\n",max(ans,Solve(2,n,1,n-1))),0;
}