从决策单调性到四边形不等式

今天上课浅学了一下，还是有点懵，于是就准备用这篇博文整理一下。
本篇文章主要讨论四边形不等式在有关 1D/1D 类问题中的应用，区间类暂不涉及。
参考：OI-Wiki

引入

我们为什么需要决策单调性？
我们之前常见的 dp 优化有很多，如单调队列，如斜率优化，如矩阵优化，等等。但是，这些优化都无法解决一些更普遍的方程，这类方程形如（这里以最小值为例）：

\[f_i = \min{f_j+w(j, i)(1 \leq j <i)} \]

或者，我们改写为区间的形式，那么就是：

\[f_r = \min{f_l+w(l, r)(1 \leq l <r)} \]

这里的 $w(l, r)$ 是一个关于 $l, r$ 的二元函数，当 $w(j, i)$ 满足 $k*g(j)+c(i)+c(j)$ 的时候，我们可以考虑斜率优化；但如果这个式子并不是这么优美，我们就似乎有点无从下手了，这时候就可以考虑决策单调性了。注意，并不是所有题目都存在决策单调性的。

四边形不等式

定义

若 $\forall l_1 \leq l_2 \leq r_1 \leq r_2$，均满足 $w(l_1, r_1) + w(l_2, r_2) \leq w(l_1, r_2) + w(l_2, r_1)$，则称函数 $w$ 满足四边形不等式（简记为“交叉小于包含”）。若等号永远成立，则称函数 $w$ 满足四边形恒等式。

性质（这里只列出两个我认为会用到的）

若函数 $w_1, w_2$ 均满足四边形不等式，则对于 $\forall c_1, c_2 \geq 0 $，函数 $c_1w_1+c_2w_2$ 也满足四边形不等式。
若存在函数 $f(x), g(x)$，使得 $w(l, r) = f(r)-g(l)$，则函数 $w$ 满足四边形恒等式。
可以通过定义证明。

决策单调性

判定

那么，四边形不等式是如何应用到决策单调性上的呢？
结论：如果函数 $w$ 满足四边形不等式，则 $f_r = \min{f_l+w(l, r)} $ 满足决策单调性。
简要证明：
我们不妨设 $l_1, l_2$ 为两个决策点，且 $l_1 < l_2$，当前要决策的点为 $r_1， r_2$，同样，$r_1 < r_2$。如果不满足决策单调性，当且仅当 $f_{r_1} + w(l_2, r_1) \leq f_{r_1} + w(l_1, r_1)$，且 $f_{r_2} + w(l_1, r_2) \leq f_{r_2} + w(l_2, r_2)$
我们令不等式上下相加、消元，就得到 $w(l_2, r_1) + w(l_1, r_2) \leq w(l_1, r_1) + w(l_2, r_2)$，与条件“满足四边形不等式”相矛盾。
有了这个性质，我们就可以搞出来一个题是否具有决策单调性了。

求解

光能推出来决策单调性还不够，我们要去用这个性质。
这里给出递归求解的过程。
我们考虑分治，令 $lq, rq$ 为我们处理的区间，$l, r$ 为最优决策点所在的区间，每次都暴力找出来处理区间的中点所对应的最优决策点，然后就可以缩小其他点的决策范围了。递归的层数只有 $\log n$ 层，所以暴力枚举的每个点都只会被枚举到 $\log n$ 次，因此复杂度是 $n \log n$ 级别的。
代码：

void solve1(int ql, int qr, int l, int r){//处理的dp区间与最优决策点所在区间 
	if(ql>qr) return;
	int mid = (ql+qr)>>1;
	int pos = 0;
	int limi = min(mid-1, r);
	for(int i = l; i<=limi; ++i){
		double tmp = W1(i, mid);
		if(tmp>f[mid]) f[mid] = tmp, pos = i;
	}
	solve1(ql, mid-1, l, pos);
	solve1(mid+1, qr, pos, r);
}

例题

Lightning Conductor
首先这和高中一类数学题很像：恒成立问题。于是我们自然而然想到要分离变量，于是有 $p \geq -a_i+a_j+\sqrt{\lvert i-j \rvert} $，于是题目变成我们去求后面部分的最大值。绝对值不好处理，我们分开来看。这里只讨论 $i > j $ 的情形。
由四边形不等式的性质，我们发现 $w(i, j) = -a_i+a_j+ \sqrt{i-j}$ 符合四边形不等式，于是就可以利用上述方法直接 dp 即可。注意这里不能一开始就取整。
代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+10;

inline int read(){
	int x = 0; char ch = getchar();
	while(ch<'0' || ch>'9') ch = getchar();
	while(ch>='0'&&ch<='9') x = x*10+ch-48, ch = getchar();
	return x;
} 

int a[N], n;
double W1(int l, int r){
	return a[l]-a[r]+1.0*sqrt(r-l);
}
double W2(int r, int l){
	return a[r]-a[l]+1.0*sqrt(r-l);
}

double f[N], g[N];
void solve1(int ql, int qr, int l, int r){//处理的dp区间与最优决策点所在区间 
	if(ql>qr) return;
	int mid = (ql+qr)>>1;
	int pos = 0;
	int limi = min(mid-1, r);
	for(int i = l; i<=limi; ++i){
		double tmp = W1(i, mid);
		if(tmp>f[mid]) f[mid] = tmp, pos = i;
	}
	solve1(ql, mid-1, l, pos);
	solve1(mid+1, qr, pos, r);
}	
void solve2(int ql, int qr, int l, int r){
	if(ql>qr) return;
	int mid = (ql+qr)>>1;
	int pos = 0;
	int limi = max(mid+1, l);
	for(int i = r; i>=limi; --i){
		double tmp = W2(i, mid);
		if(tmp>g[mid]) g[mid] = tmp, pos = i;
	}
	solve2(mid+1, qr, pos, r);
	solve2(ql, mid-1, l, pos);
}
int main(){
	n = read();
	for(int i = 1; i<=n; ++i){
		a[i] = read();
	}
	solve1(1, n, 1, n);
	solve2(1, n, 1, n);
	for(int i = 1; i<=n; ++i){
		printf("%d\n", (int)ceil(max(f[i], g[i])));
	}
	return 0;
}