区间
NKOJ传送门
description
给定\(n\)段区间\([l_i,r_i]\)。从中选择若干段(至少2段)区间，最大化它们的交集长度与并集长度的乘积。
solution
首先只会选恰好2段。
因为如果选多段，删边不会让交集长度变小，留下左端点最小的边和右端点最大的边并集也不会改变，所以可以用2段替代不劣与多段。
分类讨论两端关系
- 包含：
按r从小到大排序（r相等按l从大到小排序），然后树状数组维护左端点的最大len，每次查询时，所有它能包含的都已经在树状数组里了，只用查询左端点>=它的左端点的maxlen，然后乘自己的长度即可。就需要后缀max树状数组。 - 不包含：
首先满足包含关系的一对区间删去短的一段，构成了\(l\)和\(r\)都单增的不存在包含关系的区间。
此时对于选择区间\(i,j(i>j)\)答案是\((r_i-l_j)*(r_j-l_i)\)
还要\(i\),\(j\)不相交，发现答案值是负数不影响结果。
此时这个类似二次函数的东西是有决策单调性（单增）。我不会证！不会！
于是整体二分即可。
code
点击查看代码
#include
using namespace std;
typedef long long ll;
const int N=2e6+5;
struct node {int l,r;}Q[N],A[N];
bool cmp(node u,node v) {return u.r==v.r?u.l>v.l:u.rQ[i].l) {ans=max(ans,1ll*len*Ask(Q[i].l));A[++m]=Q[i];}
else Update(Q[i].l,len);
}
}
ll calc(int j,int i) {
return 1ll*(A[i].r-A[j].l)*(A[j].r-A[i].l);
}
void solve(int L,int R,int l,int r) {
if(l>r)return;
if(L==R) {for(int i=l;i<=r;i++)ans=max(ans,calc(L,i));return;}
int mid=(l+r)>>1,pos;ll mx=-1e18;
for(int i=L;i<=min(mid-1,R);i++) {
ll w=calc(i,mid);
if(mx