1. Description

在一个 $m\times m$ 的正方形中，给定 $n$ 个横，纵坐标均不相等的关键点。

现在有两个人从左下角 $(0,0)$ 的位置出发，前往右上角 $(m,m)$ 的位置，他们只会向上或者向右走，并且会让两人连线扫过的面积尽可能大。

现在要求求出一个点集 $S$，在两人的路径都经过这个点集中的点且 $S$ 尽可能大的前提下，使得两人连线扫过的面积尽可能小。

2. Solution

由于两人只会向上或向右走，因此点集 $S$ 中的点必须 $x$ 坐标递增，$y$ 坐标递增，那么 $S$ 的最大大小就是以 $x$ 为下标，$y$ 为权值的 LIS 的长度，这可以使用一个 $O(n\log n)$ 的算法求出，同时也可以求出一个 $LIS_i$ 表示以 $i$ 结尾的 LIS 的长度，这比较简单，就不细说了。

同时由于两人会让连线扫过的面积尽可能大，而两人一定会同时经过点集中的点，所以扫过的面积一定是若干个矩形的面积之和，这也是显然的。

因此我们得到了一个 $O(n^2)$ 的 DP 做法，将所有关键点按照 $x$ 坐标从小到大排序之后，假定 $f_i$ 表示点集以第 $i$ 个点结尾的最小代价，那么 $f_{i}=\min_{j=1}^{i-1} f_j+(x_i-x_j)\times (y_i-y_j)$ 其中 $j$ 需要满足 $y_j<y_i$ 且 $LIS_j=LIS_i-1$。

这个时间复杂度显然还不够优秀，因此我们考虑优化。

首先，由于 $i$ 只能从 $LIS_j=LIS_i-1$ 的 $j$ 转移过来，所以我们将所有关键点按照 $LIS$ 分层，转移只在层与层之间进行，那么显然的，同一层的关键点 $x$ 递增而 $y$ 递减，这十分好理解，因为如果在同一层中存在 $i,j$ 使得 $x_i<x_j$ 且 $y_i<y_j$，那么 $LIS_j\ge LIS_i+1$， $j$ 显然不应该出现在这一层。

然后我们尝试证明，对于处于同一层的 $i,j$ 如果都可以从上一层 $[l,r]$ 转移过来，那么当 $i<j$ 的时候，决策点递减，换句话说，如果假设 $i$ 的最优决策点为 $p$，$j$ 的最优决策点为 $q$，证明 $p>q$。

由于 $p$ 是 $i$ 的最优决策点，$q$ 是 $j$ 的最优决策点，那么就有：

$$f_{p}+(x_i-x_p)\times (y_i-y_p)<f_q+(x_i-x_q)\times (y_i-y_q)\\ f_{p}+(x_j-x_p)\times (y_j-y_p)>f_q+(x_j-x_q)\times (y_j-y_q)\\$$

上下相加即有：

$$f_{p}+(x_i-x_p)\times (y_i-y_p)+f_q+(x_j-x_q)\times (y_j-y_q)<f_q+(x_i-x_q)\times (y_i-y_q)+f_{p}+(x_j-x_p)\times (y_j-y_p)\\$$

也就是：

$$-x_iy_p-x_py_i-x_jy_q-x_qy_j<-x_iy_q-x_qy_i-x_jy_p-x_py_j$$

整理两边则有：

$$(x_i-x_j)(y_p-y_q)+(y_i-y_j)(x_p-x_q)>0$$

由于 $i<j$，由同一层的关键点 $x$ 递增而 $y$ 递减可以得到 $x_i-x_j<0,y_i-y_j>0$，因为这个式子大于 $0$，而 $y_p-y_q$ 与 $x_p-x_q$ 的正负性不同，所以 $x_p-x_q>0,y_p-y_q<0$，由此得到 $p>q$。

但是现在有一个问题，就是从 $j$ 转移到 $i$ 还要满足 $x_j<x_i$ 且 $y_j<y_i$，这反映到上一层的点中相当于一个区间。

因为 $x_j$ 递增，所以满足 $x_j<x_i$ 的点一定是一个形如 $[1,r]$ 的区间，同理因为 $y_j$ 递减，所以满足 $y_j<y_j$ 的点一定是一个形如 $[l,tot]$ 的区间，那么可以转移到 $i$ 的 $j$ 的区间就是 $[l,r]$。

而当 $i$ 增大的时候，整个区间整体右移，这显然是没有办法直接利用决策单调性写的，因为我们上面的证明基于：

处于同一层的 $i,j$ 如果都可以从上一层 $[l,r]$ 转移过来

所以我们需要让所有 $[l,r]$ 相同的 $i$ 放在一起，才可以利用决策单调性来写。

但是如果不做任何处理的话，时间复杂度就退化为 $O(n^2)$ 的了，这显然是无法接受的，因此要对 $i$ 的转移区间进行分割，然后分别求解，由此，我们联想到了线段树分治，也就是将询问挂在线段树上，那么在同一个节点上的询问就可以利用决策单调性来写了，具体可以使用分治来解决。

时间复杂度为 $O(n\log^2n)$，显然是可以通过此题了。

3. Code

/*by qwer6*/
/*略去缺省源与快读快写*/
const int N=2e5+5,M=1e6+5;
int n,m,len,tot;
ll ans;
int f[N];
pii a[N];
ll g[N];
vector<int>level[N];
struct Node{
	int ls,rs;
	vector<int>q;
	void init(){
		ls=rs=0;
		q.clear();
	}
}tree[N<<1]; 
#define mid (l+r>>1)
int New(){
	tree[++tot].init();
	return tot;
}
void change(int &p,int l,int r,int L,int R,int v){
	if(!p)p=New();
	if(L<=l&&r<=R){
		tree[p].q.push_back(v);
		return ;
	}
	if(mid>=L)change(tree[p].ls,l,mid,L,R,v);
	if(mid<R)change(tree[p].rs,mid+1,r,L,R,v);
}
void CDQ(int idx,int p,int l,int r,int L,int R){
	if(l>r)return ;
	ll mi=8e18;
	int x=tree[p].q[mid],place;
	for(int i=L,y;i<=R;i++){
		if(mi>cal(x,level[idx][i])){
			mi=cal(x,level[idx][i]);
			place=i;
		}
	}
	tomin(g[x],mi);
	CDQ(idx,p,l,mid-1,place,R);
	CDQ(idx,p,mid+1,r,L,place);
}
void dfs(int idx,int p,int l,int r){
	if(!p)return ;
	CDQ(idx,p,0,tree[p].q.size()-1,l,r); 
	if(l==r)return ;
	dfs(idx,tree[p].ls,l,mid),dfs(idx,tree[p].rs,mid+1,r);
}
#undef mid
int findL(int idx,int x){
	int l=0,r=level[idx].size()-1,res=level[idx].size();
	while(l<=r){
		int mid=l+r>>1;
		if(a[level[idx][mid]].second<a[x].second){
			res=mid;
			r=mid-1;
		}else l=mid+1;
	}
	return res;
}
int findR(int idx,int x){
	int l=0,r=level[idx].size()-1,res=-1;
	while(l<=r){
		int mid=l+r>>1;
		if(a[level[idx][mid]].first<a[x].first){
			res=mid;
			l=mid+1;
		}else r=mid-1;
	} 
	return res;
}
signed main(){
	read(n),read(m);
	for(int i=1;i<=n;i++)
		read(a[i].first),read(a[i].second);
	sort(a+1,a+n+1);
	for(int i=1,p;i<=n;i++){
		if(len==0||f[len]<a[i].second){
			f[++len]=a[i].second;
			level[len].push_back(i);
			continue;
		}
		p=lower_bound(f+1,f+len+1,a[i].second)-f;
		f[p]=a[i].second,level[p].push_back(i);
	}
	memset(g,0x3f,sizeof(g));
	for(int x:level[1])g[x]=1ll*a[x].first*a[x].second;
	for(int idx=2,rt,l,r,R;idx<=len;idx++){
		rt=0,R=level[idx-1].size()-1,l=r=-1;
		for(int x:level[idx]){
			while(l<R&&a[level[idx-1][l+1]].second>a[x].second)l++;
			while(r<R&&a[level[idx-1][r+1]].first<a[x].first)r++;
			change(rt,0,R,l+1,r,x);
		}
		dfs(idx-1,rt,0,R);
	}
	ans=8e18;
	for(int x:level[len])
		tomin(ans,g[x]+1ll*(m-a[x].first)*(m-a[x].second));
	write(ans);	
}