切比雪夫距离与曼哈顿距离

内含高维曼哈顿-切比雪夫转换。

定义

曼哈顿距离：$|x_1-x_2|+|y_1-y_2|$

切比雪夫距离：$\max(|x_1-x_2|,|y_1-y_2|)$

更多距离

欧几里得距离：$\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$

$L_m$ 距离：$(|x_1-x_2|^m+|y_1-y_2|^m)^{\frac{1}{m}}$

$n$ 维欧几里得距离：$\sqrt{\sum_{i=1}^n(d_{i1}-d_{i2})^2}$

$n$ 维曼哈顿距离：$\sum_{i=1}^n|d_{i1}-d_{i2}|$

$n$ 维切比雪夫：$\max_{i=1}^n|d_{i1}-d_{i2}|$

转换

曼哈顿转切比雪夫：$(x,y)\rightarrow(x+y,x-y)$

切比雪夫转曼哈顿：$(x,y)\rightarrow(\frac{x+y}{2},\frac{x-y}{2})$

证明

证明可以用几何，因为曼哈顿坐标系是通过切比雪夫坐标系旋转 $45^\circ$ 后，再缩小到原来的一半得到的。

或者纯代数，$x\leq y$ 时 $|x-y|=x-y$，$x<y$ 时 $|x-y|>x-y$，转换成 $(x+y,x-y)$ 之后 $\max(|x_1-x_2|,|y_1-y_2|)$ 一定是原来的 $|x_1-x_2|+|y_1-y_2|$ 都取到绝对值的时候，也就是曼哈顿距离，而 $\max(|x_1-x_2|,|y_1-y_2|)$ 就是切比雪夫距离。

其实是转换成 $(x,y),(-x,y),(x,-y),(-x,-y)$，因为切比雪夫本身有绝对值所以正负效果是一样的，去掉重复一半的就是上面的式子。

切比雪夫转曼哈顿其实就是解 $\begin{cases}x+y=a\cr x-y=b\end{cases}$ 的方程。

高维切比雪夫和曼哈顿

通过上面的证明可以得到，$k$ 维曼哈顿可以转换为 $2^{k-1}$ 维的切比雪夫。

也就是指定每一位取正还是取负，在去掉重复的 $\frac{1}{2}$。

但是高维切比雪夫却不一定都能转换为曼哈顿，因为本质这个转换是解方程，拿四维切比雪夫 $(a,b,c,d)$ 举例

$$\begin{cases} x+y+z=a\cr -x+y+z=b\cr x-y+z=c\cr x+y-z=d \end{cases}$$

这个方程需要满足 $a=b+c+d$ 才能有解，有解情况下

$$\begin{cases} x=\frac{a-b}{2}\cr y=\frac{a-c}{2}\cr z=\frac{a-d}{2} \end{cases}$$

而切比雪夫不是 $2^k$ 维的情况下我们可以升维成 $2^k$ 维，这个时候补 $0$ 也有可能使得方程一定有解。

比如求

$$\sum_{i=1}^n\sum_{j=1}^{i-1}\max(a_i-a_j,b_i-b_j,c_i-c_j)-\min(a_i-a_j,b_i-b_j,c_i-c_j)$$

可以直接 min-max 容斥，但是跑的慢

推式子

$$\begin{aligned} &\max(a_i-a_j,b_i-b_j,c_i-c_j)-\min(a_i-a_j,b_i-b_j,c_i-c_j)\cr =&\max(|b_i-b_j-(a_i-a_j)|,|c_i-c_j-(b_i-b_j)|,|a_i-a_j-(c_i-c_j)|)\cr =&max(|(b_i-a_j)+(b_j-a_j)|,|(c_i-b_i)+(c_j-b_j)|,|(a_i-c_i)+(a_j-c_j|)) \end{aligned}$$

这明显是一个三维切比雪夫，给他升成四维，令 $a=0$，刚好满足 $a=b+c+d$，所以原式为

$$\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^{i-1}|b_i-a_i|+|c_i-b_i|+|a_i-c_i|$$

这个直接排序就能求了。

补充

其实不把重复的去掉，保留 $2^k$ 维，这样就不用取 $\text{abs}$ 了，能有比切比雪夫更好的性质。