关键观察

差值公式转换： 令 $x = L_a-L_b$, $y = J_a-J_b$, $z = K_a-K_b$ 则 $D(T_a,T_b) = \max(x,y,z) - \min(x,y,z)$

与曼哈顿距离的关系：

经过数学推导，可以发现： $D(T_a,T_b) = \frac{1}{2}(|(x-y)| + |(y-z)| + |(z-x)|)$

进一步转换： 定义新的坐标变换：

$u_i = L_i - J_i$

$v_i = J_i - K_i$

$w_i = K_i - L_i$

则 $D(T_a,T_b) = \frac{1}{2}(|u_a-u_b| + |v_a-v_b| + |w_a-w_b|)$

算法思路

坐标变换：对于每个三元组 $(L_i,J_i,K_i)$，计算：

$u_i = L_i - J_i$

$v_i = J_i - K_i$

$w_i = K_i - L_i$

独立计算贡献：

由于绝对值函数在三个维度上是独立的，我们可以分别计算：

所有 $u$ 坐标两两绝对差之和

所有 $v$ 坐标两两绝对差之和

所有 $w$ 坐标两两绝对差之和

高效计算绝对差之和：

对于任意数组 $a$，所有元素对的绝对差之和可以通过排序后计算： $\sum_{i<j} |a_i - a_j| = \sum_{i=0}^{n-1} a_i \times (2i - n + 1)$

最终答案： $answer = \frac{1}{2} \times (sum_u + sum_v + sum_w) \mod (10^9+7)$

该算法的正确性基于：

数学上证明了 $D(T_a,T_b) = \frac{1}{2}(|u_a-u_b| + |v_a-v_b| + |w_a-w_b|)$

绝对值差之和可以通过排序高效计算

模运算正确处理了除2操作（使用乘法逆元）

这种方法将原本 $O(n^2)$ 的暴力计算优化到了 $O(n \log n)$，能够处理 $n \leq 5\times10^5$ 的数据规模。

复杂度分析

时间复杂度：$O(n \log n)$，主要来自三次排序

空间复杂度：$O(n)$，存储三个坐标数组