*IX. P5896 [IOI2016]aliens

DP 优化方法大杂烩，详解 wqs 二分及其注意事项，斜率优化等其它 DP 优化方法。

更好的阅读体验。

**** 团队赛 T6，没想到是 IOI 原题。当时看出来要用 wqs 二分，但是我没学过（经常发生知道要用某种算法但是不会写的情况），因此最近学习了一下 wqs 二分。找题目练手的时候看到了这题，世 界 线 收 束。做题的过程中发现还要用到斜率优化，于是也学了一下。

这算是一道比较套路的题目，但套路并不意味这不是好题，毕竟我从中学到了 wqs 二分和斜率优化两种 DP 优化方法。说它套路其实也不太合适，因为 2016 年 wqs 二分还没有在 OI 界普及，甚至国外将其称之为 “Aliens’ Trick” 就是根据本题的名字而命名的，所以这个 idea 在当时应该比较新颖。

---

不妨对网格图的主对角线所经过的格子从左上到右下依次编号为 $0,1,2,\cdots,m-1$。显然，编号为 $i$ 的格子在原网格图中的坐标为 $(i,i)$。因为正方形的主对角线完全包含于网格图的主对角线，所以为了拍到一个点 $(r_i,c_i)$ 必然要拍到编号为 $l_i,l_i+1,l_i+2,\cdots,r_i$ 的格子，其中 $l_i=\min(r_i,c_i),r_i=\max(r_i,c_i)$。因此，我们可以将题目转化为线段覆盖问题：现在有 $n$ 条线段 $[l_i,r_i]$，我们要用最多 $k$ 个区间 $[x_i,y_i]$ 去覆盖它们，使得每条线段至少被一个区间完全包含。即 $\forall i,\exist j,s.t. [l_i,r_i]\in [x_j,y_j]$。求以每个区间为对角线形成的所有正方形的面积并的最小值。接下来我们可以挖掘一些性质：

• $\textbf {Observation 1.}$ 如果两条线段 $i,j$ 满足 $[l_i,r_i]\in [l_j,r_j]$，那么线段 $i$ 对最终的答案没有影响。

  正确性显然。根据该性质，我们可以将所有线段按照左端点 $l_i$ 从小到大为第一关键字，右端点 $r_i$ 从大到小为第二关键字排序。然后依次遍历所有线段并记录右端点最大值 $r$。若当前线段 $i$ 的右端点 $r_i\leq r$，则忽略线段 $i$；否则用 $r_i$ 去更新 $r$，即 $r\gets r_i$。最终所有没有被忽略的线段，一定满足左端点和右端点都单调递增。读者自证不难。

• $\mathbf{Observation\ 2.}$ 最终所选取的所有区间一定满足 $x_i<x_{i+1},y_i<y_{i+1}\ (1\leq i<k)$。

  读者自证不难。

• $\mathbf{Observation\ 3.}$ 设 $F_i$ 为恰好选取 $i$ 个区间时答案的最小值，那么 $F_i$ 是一个下凸函数。

  读者自证不很难。感性理解一下即可，严格证明的话应该比较复杂。

有了上述性质，我们可以愉快地进行 DP 了：wqs 二分斜率 $K$，然后设 $f_i$ 表示覆盖第 $i$ 条线段时的最小代价（线段按照左端点从小到大排序。根据性质 $1$ 的结论，右端点也行，因为不影响线段之间的顺序）。显然有转移方程：

$$f_i=\min_{j=0}^{i-1}-K+\begin{cases}f_j+(y_i-x_{j+1}+1)^2-(y_j-x_{j+1}+1)^2&y_j\geq x_{j+1}\land j>0\\f_j+(y_i-x_{j+1}+1)^2&\mathrm{otherwise}\end{cases}$$

这个分情况讨论很讨厌，尝试把它消灭掉：设 $g_i=(y_i-x_{i+1}+1)^2[y_i\geq x_{i+1}\land i>0]$，那么转移方程变为 $f_i=\min_{j=0}^{i-1}f_j+(y_i-x_{j+1}+1)^2-g_j-K$。显然的斜率优化，但是我不会，所以多讲一点：拆开变成 $f_i=\min_{j=1}^{i-1} f_j+(y_i+1)^2-2(y_i+1)x_{j+1}+x^2_{j+1}-g_j-K$。先将所有 $y_i$ 加上 $1$（不影响单调性），忽略掉 $\min$ 再移移项，写成 $Y=kX+b$ 的形式，$f_j+x^2_{j+1}-g_j-K=2y_ix_{j+1}+(f_i-y_i^2)$。那么 $Y=f_j+x^2_{j+1}-g_j-K$，$k=2y_i$，$X=x_{j+1}$，$b=f_i-y^2_i$。将 $(X_j,Y_j)$ 看做一个点，因为 $k$ 确定了，现在就要找使得 $b$ 最小的 $(X_j,Y_j)$（这样能使得 $f_i$ 最小）。由于 $k,X$ 都是单调递增的，所以单调队列维护下凸包即可。

具体地，记 $k_{i,j}$ 为点 $(X_i,Y_i)$ 与 $(X_j,Y_j)$ 之间的斜率。首先将点 $0$ 加入单调队列，接下来遍历从小到大每个位置 $i$：

• 若单调队列大小不小于 $2$，设 $a,b$ 分别为队首的第一个和第二个点，若 $k_{a,b}\leq k=2y_i$ 则 $b$ 一定不劣于 $a$，弹出队首。重复该操作直到单调队列大小为 $1$ 或 $k_{a,b}>2y_i$。
• 此时队首 $a$ 即为最优决策 $j$，$f_j\to f_i$ 转移并记录选择的区间个数。
• 若单调队列大小不小于 $2$，设 $c,d$ 分别为队尾的倒数第二个和倒数第一个点；若 $k_{c,d}\geq k_{d,i}$ 则 $d$ 一定不在下凸包上，弹出队尾。重复该操作直到单调队列大小为 $1$ 或 $k_{c,d}<k_{d,i}$。
• 将点 $i$ 加入单调队列。

我们需要求出在代价最小的前提下最少的区间个数。不妨设 $num_i$ 为覆盖前 $i$ 条线段且代价最小时最少的区间个数 ，那么因为 $num_i$ 显然有单调性，所以我们每次转移时只需要选择最前面的一个决策点转移即可，即第一步操作弹出队首时，将条件 $k_{a,b}\leq 2y_i$ 改为 $k_{a,b}<2y_i$，这样就保证了相同优劣的决策点，前者不会被后者所弹出（第三步的条件不需要改，因为是前面的决策点弹出后面的决策点，不影响结果）。

时间复杂度 $\mathcal{O}(n\log V)$，其中 $V$ 是二分范围，本题中为 $m^2$。浮点数比较建议使用 $eps$。代码倒是不难写。

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ld long double

const int N=1e5+5;
const ld eps=1e-10;

ll n,m,k,c,ans;
struct seg{
	int l,r;
	bool operator < (const seg &v) const{
		return l!=v.l?l<v.l:r>v.r;
	}
}p[N];

ll K,f[N],g[N],num[N];
ll sq(ll x){return x*x;}
ll Y(int i){return f[i]+sq(p[i+1].l)-g[i]-K;}
ll X(int i){return p[i+1].l;}
ld slope(int i,int j){return (ld)(Y(j)-Y(i))/(X(j)-X(i));}

ll hd,tl,d[N];
bool check(){
	d[hd=tl=1]=0;
	for(int i=1;i<=n;i++){
		while(hd<tl&&slope(d[hd],d[hd+1])+eps<=2*p[i].r)hd++;
		int j=d[hd]; num[i]=num[j]+1,f[i]=f[j]+sq(p[i].r-p[j+1].l)-g[j]-K;
		if(i<n)while(hd<tl&&slope(d[tl-1],d[tl])-eps>=slope(d[tl],i))tl--;
		d[++tl]=i;
	} return num[n]<=k;
}

int main(){
	cin>>n>>m>>k;
	for(int i=1,c,r;i<=n;i++){
		cin>>p[i].l>>p[i].r;
		if(p[i].l>p[i].r)swap(p[i].l,p[i].r);
	} sort(p+1,p+n+1);
	for(int i=1,r=-1;i<=n;i++)if(p[i].r>r)r=p[i].r,p[++c]=p[i]; n=c;
	for(int i=1;i<n;i++)if(p[i].r>=p[i+1].l)g[i]=sq(p[i].r-p[i+1].l+1);
	for(int i=1;i<=n;i++)p[i].r++;
	ll l=-1e12,r=0;
	while(l<r)K=(l+r>>1)+1,check()?(l=K,ans=f[n]+K*k):r=K-1;
	cout<<ans<<endl;
	return 0;
}