曼哈顿距离 & 切比雪夫距离 笔记

一、定义

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

优势：容易快速计算。

具体的，sort 一遍然后用前缀和即可计算 $\sum |x_i-x_j|$。

int calc(int d[]) {
    sort(d + 1, d + n + 1);
    for (int i = 1; i <= n; i++)
        q[i] = q[i - 1] + d[i];
    int ret = 0;
    for (int i = 1; i <= n; i++)
        ret += (d[i] * i - q[i]);
    return ret * 2;
}

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

优势：限定距离后，与坐标轴平行，容易进行扫描线 / CDQ 分治。

二、转化

1. 曼哈顿距离 $\to$ 切比雪夫距离

结论：将 $(x_i,y_i)$ 转化为 $(x_i+y_i,x_i-y_i)$ 后计算切比雪夫距离。

证明：

$$\begin{array}{rl}\mathrm{dis}(i,j)& =|x_i-x_j|+|y_i-y_j|\\ & =max((x_i+y_i)-(x_j+y_j),(x_j+y_j)-(x_i+y_i),(x_i-y_i)-(x_j-y_j),(x_j-y_j)-(x_i-y_i))\\ & =max(|(x_i+y_i)-(x_j+y_j)|,|(x_i-y_i)-(x_j-y_j)|)\end{array}$$

2. 切比雪夫距离 $\to$ 曼哈顿距离

结论：将 $(x_i,y_i)$ 转化为 $(\frac{x_i+y_i}{2},\frac{x_i-y_i}{2})$ 后计算曼哈顿距离。

证明：咕咕咕。

三、应用

1. P10633 BZOJ2989 数列/BZOJ4170 极光

将曼哈顿距离转为切比雪夫距离，打上坐标系，二维差分后 CDQ 分治。