【题目来源】
AtCoder：D - Distance Between Cities
【题目描述】
Takahashi has been put in charge of urban planning for a certain region. This region has \(N\) cities, each numbered from \(1\) to \(N\).
高桥被委任负责某个地区的城市规划。这个地区有 \(N\) 个城市，每个城市编号从 \(1\) 到 \(N\)。
The position of each city \(i\) (\(1 \leq i \leq N\)) is represented by integer coordinates in \(M\)-dimensional space, where \(A_{i,k}\) denotes the coordinate value in the \(k\)-th dimension (\(1 \leq k \leq M\)).
每个城市 \(i\)（\(1 ≤ i ≤ N\)）的位置用 \(M\) 维空间中的整数坐标表示，其中 \(A_{i,k}\) 表示第 \(k\) 维（\(1 ≤ k ≤ M\)）的坐标值。
Takahashi defines the distance between two cities using the Manhattan distance. That is, the distance between city \(i\) and city \(j\) is \(\displaystyle\sum_{k=1}^{M} |A_{i,k} - A_{j,k}|\).
高桥使用曼哈顿距离来定义两个城市之间的距离。也就是说，城市 \(i\) 和城市 \(j\) 之间的距离是 \(\displaystyle\sum_{k=1}^{M} |A_{i,k} - A_{j,k}|\).。
Takahashi wants to compute the distances for all unordered pairs of distinct cities and find their total sum.
高桥想要计算所有无序的不同城市对之间的距离，并求它们的总和。
Specifically, compute the following value:
具体而言，计算以下值：
\(\sum_{1 \leq i < j \leq N} \sum_{k=1}^{M} |A_{i,k} - A_{j,k}|\)
【输入】
\(N\) \(M\)
\(A_{1,1}\) \(A_{1,2}\) \(\ldots\) \(A_{1,M}\)
\(A_{2,1}\) \(A_{2,2}\) \(\ldots\) \(A_{2,M}\)
\(\vdots\)
\(A_{N,1}\) \(A_{N,2}\) \(\ldots\) \(A_{N,M}\)
- The first line contains the number of cities \(N\) and the number of dimensions \(M\), separated by a space.
- The \(i\)-th of the following \(N\) lines (\(1 \leq i \leq N\)) contains the \(M\)-dimensional coordinate values of city \(i\): \(A_{i,1}, A_{i,2}, \ldots, A_{i,M}\), separated by spaces.
【输出】
Output the total sum of Manhattan distances over all unordered pairs of distinct cities, as a single integer on one line.
【输入样例】
3 2
1 2
4 6
7 1
【输出样例】
22
【核心思想】
-
问题分析：给定 \(N\) 个城市在 \(M\) 维空间中的坐标，需要计算所有无序城市对之间的曼哈顿距离之和。曼哈顿距离定义为 \(\sum_{k=1}^{M} |A_{i,k} - A_{j,k}|\)。由于各维度相互独立，可以将问题分解为每个维度分别计算后求和。
-
算法选择：
- 维度分解：利用曼哈顿距离的可加性，总距离 = 各维度距离之和
- 排序 + 前缀和：对每个维度的坐标排序后，利用前缀和快速计算该维度所有点对的距离之和
-
关键步骤：
- 维度独立处理：对于每个维度 \(k\)（\(1 \leq k \leq M\)）：
- 提取该维度的所有坐标值 \(A_{1,k}, A_{2,k}, \ldots, A_{N,k}\)
- 排序：将该维度的坐标值升序排序，得到 \(B_1 \leq B_2 \leq \cdots \leq B_N\)
- 前缀和预处理：计算前缀和数组 \(sa[i] = \sum_{j=1}^{i} B_j\)
- 计算该维度的贡献：对于排序后的第 \(i\) 个点 \(B_i\)，它与前面 \(i-1\) 个点的距离之和为：\[\sum_{j=1}^{i-1} (B_i - B_j) = B_i \cdot (i-1) - \sum_{j=1}^{i-1} B_j = B_i \cdot (i-1) - sa[i-1] \]
- 累加所有 \(i\) 从 \(2\) 到 \(N\) 的贡献
- 汇总答案：将 \(M\) 个维度的贡献相加，得到最终结果
- 维度独立处理：对于每个维度 \(k\)（\(1 \leq k \leq M\)）：
-
时间/空间复杂度：
- 时间复杂度：\(O(M \cdot N \log N)\)，对每个维度排序 \(O(N \log N)\)，共 \(M\) 个维度
- 空间复杂度：\(O(M \cdot N)\)，存储坐标数组和前缀和数组
-
维度分解与前缀和优化的核心思想：
- 维度独立性：曼哈顿距离在各维度上可分解，将 \(M\) 维问题转化为 \(M\) 个一维问题
- 排序降维：排序后绝对值可以去掉，\(|B_i - B_j|\) 变为 \(B_i - B_j\)（假设 \(i > j\)）
- 前缀和优化：通过前缀和将 \(O(N^2)\) 的两两计算优化为 \(O(N)\) 的线性计算
- 贡献法：计算每个元素作为"较大值"时对总距离的贡献，避免重复计算
- 适用于多维距离计算、统计问题、贡献分解等场景
【解题思路】
【算法标签】
前缀和
【代码详解】
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 200005;
int n, m, ans; // n: 序列长度，m: 维度/属性数
int a[15][N], sa[15][N]; // a: 原始数据，sa: 前缀和数组signed main()
{cin >> n >> m; // 读入序列长度和维度for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){cin >> a[j][i]; // 注意：输入存储为a[维度][索引]}}for (int j = 1; j <= m; j++) // 对每个维度分别处理{// 对第j维的所有值排序sort(a[j] + 1, a[j] + n + 1);// 计算排序后第j维的前缀和for (int i = 1; i <= n; i++){sa[j][i] = sa[j][i - 1] + a[j][i];}// 计算第j维的贡献for (int i = 2; i <= n; i++) // 注意：从i=2开始{// 公式：a[j][i] * (i-1) - sa[j][i-1]// 这计算的是排序后，a[j][i]与它前面所有元素的差之和ans += a[j][i] * (i - 1) - sa[j][i - 1];}}cout << ans << endl; // 输出结果return 0;
}
【运行结果】
3 2
1 2
4 6
7 1
22