定义
设二维平面中的两点 \(A(x_1,y_1)\)，\(B(x_2,y_2)\)，定义它们之间的切比雪夫距离为
切比雪夫距离与曼哈顿距离
思考一下两者的联系。
\(A\) 和 \(B\) 的曼哈顿距离：
这是 \((x_1+y_1,x_1-y_1)\) 和 \((x_2+y_2,x_2-y_2)\) 的切比雪夫距离。
这说明切比雪夫坐标系是由曼哈顿坐标系旋转 \(45^{\circ}\) 后放大一倍得到的。同理：
- 曼哈顿坐标系是通过切比雪夫坐标系旋转 \(45^\circ\) 后再缩小为一半得到的。
\(A\) 和 \(B\) 的切比雪夫距离：
上面这个式子的正确性值得思考一下。
这是 \((\frac{x_1+y_1}{2},\frac{x_1-y_1}{2})\) 和 \((\frac{x_2+y_2}{2},\frac{x_2-y_2}{2})\) 的曼哈顿距离。
两者的相互转化
-
曼哈顿距离 \(\rightarrow\) 切比雪夫距离：\((x,y)\rightarrow(x+y,x-y)\)
-
切比雪夫距离 \(\rightarrow\) 曼哈顿距离：\((x,y)\rightarrow(\frac{x+y}{2},\frac{x-y}{2})\)
可惜的是在 \(D\ge 3\) 的时候切比雪夫距离不能转化为曼哈顿距离。
题目
P4648 [IOI2007] pairs 动物对数
给定 \(B\) 维曼哈顿坐标系上的 \(n\) 个整点，问满足 \(i<j,dis(i,j)\le D\) 的 \((i,j)\) 总数。
\(1\le B\le 3\)，\(n\le 10^5\)，\(D\le 10^8\).
保证点的坐标为正整数。记 \(m\) 为最大的坐标值。
-
\(B=1\)，\(m\le 7.5\times 10^7\).
-
\(B=2\)，\(m\le 7.5\times 10^4\).
-
\(B=3\)，\(m\le 75\).
\(B=1\)
双指针维护一下即可。时间复杂度 \(O(n)\).
\(B=2\)
先曼转切，令 \((x,y)\leftarrow(x+y,x-y)\).
直观的来说就是对每个 \((x,y)\) 求左上角为 \((x-D,y-D)\)，右下角为 \((x+D,y+D)\) 的子矩阵和 \(-1\).
以 \(x\) 为关键字排序，记录双指针 \(i,j\)，用树状数组维护。
偏移量设为 \(m\) 即可。时间复杂度 \(O(n\log m)\).
\(B=3\)
曼哈顿坐标系上的点可以转化为一个四元组，但是写起来太麻烦了。
不妨对 \(m=75\) 这个限制做一些暴力。
对 \((x,y,z)\) 的前二维曼转切，视为 \(z\) 平面上的点。
对于每个点 \((x_i,y_i,z_i)\)，枚举另一个点的 \(z_j\)，即求 \(z_j\) 平面上，左上角为 \((x_i-l,y_i-l)\)，右下角为 \((x_i+l,y_i+l)\) 的子矩阵和 \(-[z_i=z_j]\).
对每个平面计算其二维前缀和，时间复杂度 \(O(m^3+nm)\).
此时计算的点对总数应 \(/2\).
P3964 [TJOI2013] 松鼠聚会
给出切比雪夫坐标系上的 \(n\) 个整点，找到一个点满足其与其他点的总距离最小，输出这个值。
\(n\le 10^5\)，\(|x|,|y|\le 10^9\).
切转曼，对于点 \(j\)，求和式即
只考虑 \(x\)，可以拆成
容易发现就是前缀和。时间复杂度 \(O(n\log n)\).