题解：棋盘王棋距离和的高效计算

---

问题分析

本题要求计算两个玩家的所有王棋之间的两两距离之和，其中距离定义为切比雪夫距离（Chebyshev距离）：

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

朴素计算需要 $O(k^2)$ 时间（$k$ 为棋子数），不可行。需要优化到 $O(RC)$。

---

核心观察与坐标变换

1. 坐标变换

关键技巧：引入变换坐标：

• $u = x + y$
• $v = x - y$

在变换后，切比雪夫距离转化为曼哈顿距离的一半：

$$\max(|dx|,|dy|) = \frac{|du| + |dv|}{2}$$

2. 距离和分解

对于棋子集合，总距离和：

$$\sum_{i<j} \max(|dx|,|dy|) = \frac{1}{2} \left( \sum_{i<j} |u_i-u_j| + \sum_{i<j} |v_i-v_j| \right) $$

问题分解为两个一维绝对差和问题。

3. 一维绝对差和计算

对于一维点集 $p_1, p_2, \dots, p_k$（已排序）：

$$\sum_{i<j} |p_i-p_j| = \sum_{i=1}^k p_i \cdot (2i - k - 1) $$

推导：排序后 $p_1 \le p_2 \le \dots \le p_k$， 对于 $p_i$，有 $i-1$ 个点比它小，$k-i$ 个点比它大，所以贡献为 $p_i \cdot [(k-i) - (i-1)] = p_i \cdot (k-2i+1)$。

---

算法框架

第一步：收集坐标并变换

代码中的巧妙处理：

1. 第一次扫描：按对角线 $x+y = const$ 收集点，计算 $u$ 坐标的贡献

   • 对于满足 $x+y = s$ 的点，$u = s$ 为常数
   • 实际上这里计算的是 $u$ 坐标的绝对差和
   • 但代码通过特殊方式避免了显式存储所有点

2. 第二次扫描：按对角线 $x-y = const$ 收集点，计算 $v$ 坐标的贡献

第二步：一维距离和计算

函数 get(point *poi, int n, bool calx)：

• 如果 calx = true：按 $u$ 坐标排序并计算 $\sum |u_i-u_j|$
• 如果 calx = false：按 $v$ 坐标排序并计算 $\sum |v_i-v_j|$

实现方式：

ll get(point *poi, int n, bool calx) {
    ll ret = 0, got = 0;
    if (calx)
        for (int i = 1; i <= n; i++)
            ret += 1ll * (i - 1) * poi[i].x - got, got += poi[i].x;
    else
        for (int i = 1; i <= n; i++)
            ret += 1ll * (i - 1) * poi[i].y - got, got += poi[i].y;
    return ret;
}

这里利用了公式 $\sum_{i<j} |p_i-p_j| = \sum_{i=1}^k p_i \cdot (2i-k-1)$，但实现更简洁：

$$ret = \sum_{i=1}^k [(i-1) \cdot p_i - (p_1 + \dots + p_{i-1})] $$

等价于 $\sum_{i=1}^k p_i \cdot (i-1) - \sum_{j=1}^{i-1} p_j$。

第三步：合并结果

总距离和 = $(u\text{坐标贡献} + v\text{坐标贡献}) / 2$

---

代码细节解析

第一次扫描

for (int x = 2; x <= n + m; x++)  // x = x+y 的和
    for (int i = 1; i <= n; i++) {
        if (x - i >= 1 && x - i <= m) {  // 计算 y = x-i
            if (mp[i][x - i] == 'M')
                mir[++mcnt] = (point){x, x - 2*i};  // 存储 (u, v)
        }
    }

这里：

• x 是 $u = x+y$ 的值
• x - 2*i = (x+y) - 2x = y - x = -v，但符号不影响绝对差

实际上存储的是变换后的坐标，但为了计算 $u$ 坐标差，只用了第一个分量。

第二次扫描

for (int y = 1 - m; y <= n - 1; y++)  // y = x-y 的差
    for (int j = 1; j <= m; j++) {
        if (y + j >= 1 && y + j <= n) {  // 计算 x = y+j
            if (mp[y + j][j] == 'M')
                mir[++mcnt] = (point){y + 2*j, y};  // 存储 (u, v)
        }
    }

排序隐含

注意：get 函数假设输入数组已按相应坐标排序。由于扫描时是按特定顺序（对角线顺序），得到的数组可能已经有序，或需要显式排序（代码中未显示排序，可能依赖输入特性）。

---

复杂度分析

• 时间复杂度：$O(RC)$
  • 两次扫描棋盘：$O(RC)$
  • get 函数：$O(k)$，$k$ 为棋子数
• 空间复杂度：$O(RC)$ 存储所有棋子

对于 $R,C \le 1000$，$RC \le 10^6$，完全可行。

---

正确性证明

1. 坐标变换的正确性

切比雪夫距离与曼哈顿距离关系：

$$\max(|dx|,|dy|) = \frac{|dx+dy| + |dx-dy|}{2} = \frac{|du|+|dv|}{2} $$

2. 距离和分解

由于绝对值函数的线性可加性：

$$\sum_{i<j} \frac{|du|+|dv|}{2} = \frac{1}{2}\left(\sum_{i<j}|du| + \sum_{i<j}|dv|\right) $$

3. 一维公式的正确性

对于排序后的 $p_1 \le p_2 \le \dots \le p_k$：

$$\sum_{i<j} (p_j - p_i) = \sum_{i=1}^k p_i \cdot [(k-i) - (i-1)] = \sum_{i=1}^k p_i \cdot (k-2i+1) $$

代码中的公式是等价变形。

---

算法优势

1. 避免显式两两计算：将 $O(k^2)$ 降为 $O(k)$
2. 分离坐标维度：二维问题分解为两个一维问题
3. 利用扫描顺序：可能避免显式排序
4. 内存高效：只需要存储棋子坐标，无需邻接矩阵

---

总结

本题是一道距离计算优化的经典问题，主要考察：

1. 坐标变换技巧：Chebyshev距离到曼哈顿距离的转化
2. 一维距离和公式：排序后线性计算绝对差和
3. 扫描线思想：按对角线收集点，可能自然有序
4. 问题分解能力：将复杂二维问题分解为简单一维问题

算法的核心在于通过巧妙的坐标变换，将难以直接计算的二维距离和转化为两个一维绝对差和，从而大幅降低时间复杂度。

这种"坐标变换+一维公式"的方法是计算几何和组合优化中的常用技巧，适用于各种距离度量下的聚合计算。