$Result$

---

$Hyperlink$

https://www.luogu.com.cn/problem/P2900

---

$Description$

有$n$块土地，第$i$块土地的长为$x_i$，宽为$y_i$ ，现需将这些土地分成若干组，分成一组将产生这一组内长的最大值$\times$宽的最大值的代价，试确定一种分组方案，使得总代价最小

数据范围：$n\le 5\times 10^4,x_i,y_i\le 10^6$

---

$Solution$

将每个土地的长和宽抽象的看做是一个点$(x,y)$，注意到如果存在两个点$A(x,y),B(x^{‘},y^{‘})$满足$x\le x^{‘},y\le y^{‘}$，则$A$这个点是可以舍弃的，因为显然当且仅当把它和$B$划分到一起答案会更优。

如果我们把所有矩形按照$x$为第一关键字升序排序，剩下来的点在第一象限中就构成了阶梯型。

设$f_i$表示划分到第$i$个矩形的最优代价
显然枚举$j$表示把$[j+1\sim i]$划分到一起得到方程 f i = m i n { f j + y j + 1 × x i } f_i=min\{f_j+y_{j+1}\times x_i\} fi​=min{fj​+yj+1​×xi​}【$x$递增，所以最大值在$i$取，$y$递减，所以最大值在$j+1$取】

可以证明或打表发现$f_j$后面那坨满足四边形不等式，即$f$具有决策单调性

如此，我们只需考虑每个决策对后续转移的影响，然后二分出决策的赚一点即可

时间复杂度：$O(n{\log }_{2}n)$

---

$Code$

#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
#define LL long long
#define N 50010
using namespace std;int n,m,tl,hd,maxl;
struct node{LL x,y;}a[N];
struct note{int l,r,x;}que[N];
inline bool cmp(node x,node y){return x.x<y.x||x.x==y.x&&x.y>y.y;}
LL f[N];
inline LL read()
{char c;LL d=1,f=0;while(c=getchar(),!isdigit(c)) if(c=='-') d=-1;f=(f<<3)+(f<<1)+c-48;while(c=getchar(),isdigit(c)) f=(f<<3)+(f<<1)+c-48;return d*f;
}
inline LL Cost(int i,int j){return f[i]+a[i+1].y*a[j].x;}
inline int findx(int i)
{int L=que[tl].l,R=que[tl].r,mid;while(L<=R){mid=L+R>>1;if(Cost(i,mid)<Cost(que[tl].x,mid)) R=mid-1;else L=mid+1;}return L;
}
signed main()
{n=read();for(register int i=1;i<=n;i++) a[i].x=read(),a[i].y=read();sort(a+1,a+1+n,cmp);for(register int i=1;i<=n;i++){while(m&&a[m].y<=a[i].y) m--;a[++m]=a[i];}que[hd=tl=1]=(note){1,m,0};for(register int i=1;i<=m;i++){while(hd<=tl&&que[hd].r<i) hd++;f[i]=Cost(que[hd].x,i);while(hd<=tl&&i<que[tl].l&&Cost(i,que[tl].l)<Cost(que[tl].x,que[tl].l)) tl--;int u=findx(i);que[tl].r=u-1;if(u<=m) que[++tl]=(note){u,m,i};}printf("%lld",f[m]);
}