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

· · 算法·理论

例题：给出二维平面上 n 个点，多次询问，查询编号 [l,r] 内的点两两曼哈顿距离的最小值。

两点 A(x_1,y_1),B(x_2,y_2) 的曼哈顿距离为：

|x_1-x_2|+|y_1-y_2| =\max(x_1-x_2,x_2-x_1)+\max(y_1-y_2,y_2-y_1) =\max(x_1+y_1-x_2-y_2,x_2+y_2-x_1-y_1,x_1+y_2-x_2-y_1,x_2+y_1-x_1-y_2)

令 C(x_1+y_1,x_1-y_1),D(x_2+y_2,x_2-y_2)，则 C,D 的切比雪夫距离为：

\max(|x_1+y_1-x_2-y_2|,|x_1+y_2-x_2-y_1|) =\max(x_1+y_1-x_2-y_2,x_2+y_2-x_1-y_1,x_1+y_2-x_2-y_1,x_2+y_1-x_1-y_2)

会发现 A,B 的曼哈顿距离，就等于 C,D 的切比雪夫距离。

回到题目，把给出的点 (x,y) 变为 (x+y,x-y) 形式，第二个操作变为查询区间内两两切比雪夫距离的最小值。因为切比雪夫的定义是 x 坐标差与 y 坐标差的 \max，所以只需要维护区间内 x,y 坐标分别的最大、最小值，RMQ 做即可。

这个小 trick 也算比较常用的了，常搭配一些数据结构或其他技巧来出题。

习题：