这是官方题解的 AI 中文翻译

完整解法 1（Alan）：

（注：部分断言的证明留作读者练习。）

在镶嵌结构中，两种类型的边各自形成独立的网格。连接整数点 $x + y \exp(\pi i / 3)$ 的边构成一个等边三角形网格；连接等边三角形中心的边则构成一个菱形网格。

请注意，在原始镶嵌结构中，两点之间的距离等于两个子网格中距离之和。因此，我们可以分别独立计算两个子网格中的成对距离之和，再将它们相加。

我们首先计算等边三角形网格中的距离。给定网格中的两个点，它们之间水平网格线的数量等于最短路径中穿过的水平边的数量。这使我们能够计算总的水平边穿越次数。

按 $y$ 坐标遍历所有点。在两个连续的 $y$ 值之间，每条水平网格线被穿越的次数为 $b \cdot (N - b)$，其中 $b$ 是该线以下的点的数量。其他两个方向的边穿越次数可类似计算。

现在，我们计算菱形网格中的距离。我们可以将该网格划分为两个六边形网格，划分依据是边连接的是朝上还是朝下的等边三角形的中心。设朝上的六边形表示那些外接朝上三角形的六边形。例如，点 $(0, 0, 0)$ 与 $(1, 1, 7)$ 之间的最短路径在等边三角形网格、朝上六边形网格和朝下六边形网格中各穿过一条边。

要计算六边形网格中的距离，需注意它实际上可归约为等边三角形网格。对于朝上六边形网格中的两点，它们之间的距离等于对应内接朝上三角形中两点距离的一半。这是因为穿越六边形网格中的一条边，可视为先穿越一条边进入一个朝下三角形，再穿越一条边离开它。

然而，这里有一个棘手的问题。两个六边形网格并非独立的，这意味着菱形网格中的距离并不总是两个六边形网格中距离之和。为说明这一点，考虑点 $(0, 0, 0)$ 与 $(0, 0, 5)$。最短路径中每个六边形网格恰好穿越一条边。但另一方面，任何路径必须在一个网格中穿越两个六边形。因此，真实距离为 $1 + 2$，而非 $1 + 1$。

我们可以将此问题描述为单边情形。考虑所有具有水平长对角线的菱形集合。它们可被划分为无限条共享一个顶点的链。例如，点 $(0, 0, 0), (1, 0, 0), (2, 0, 0), \ldots$ 位于同一条菱形链中。

断言：在同一条链中，两个位于不同菱形内的点之间的距离，总是比它们在六边形网格中的距离之和恰好大 1。

证明：到达链中第 $r$ 个菱形的距离为 $2r + 1$，但在六边形网格中的距离均为 $r$。

我们可以通过按每条链中的菱形计数点来计算这些值。对于每条链，若菱形中包含 $a_1, \ldots, a_m$ 个点，则我们需要加上

$$\binom{a_1 + \cdots + a_m}{2} - \sum_{i=1}^{m} \binom{a_i}{2}.$$

该表达式计算的是点对的总数，再减去位于同一菱形内的点对数。

对于另外两个方向上的链，同样适用此结论。在菱形网格中不存在其他边界情况。该解法的时间复杂度为 $O(N \log N)$。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

void solve() {
  int n;
  cin >> n;
  vector<array<int, 3>> p(n);
  for (auto &[x, y, z] : p)
    cin >> x >> y >> z;

  // compute sum of pairwise abs difference given map of counts
  auto calc_dir = [&](map<int, int> &m) {
    ll ret = 0;
    int pos = m.begin()->first;
    int cnt = m.begin()->second;
    m.erase(m.begin());
    for (auto [k, v] : m) {
      ret += ll(k - pos) * cnt * (n - cnt);
      cnt += v;
      pos = k;
    }
    return ret;
  };

  // location in equilateral triangle grid
  // bool denotes inside downward-pointing triangle to the right
  vector<tuple<int, int, bool>> loc;
  // compute sum of pairwise distance in equilateral triangle grid
  auto calc = [&]() {
    ll ret = 0;

    map<int, int> m;
    for (auto [x, y, z] : loc)
      m[x]++;
    ret += calc_dir(m);

    m.clear();
    for (auto [x, y, z] : loc)
      m[y]++;
    ret += calc_dir(m);

    m.clear();
    for (auto [x, y, z] : loc)
      m[x + y + z]++;
    ret += calc_dir(m);

    return ret;
  };

  // equilateral triangle grid
  ll ans = 0;
  for (auto [x, y, z] : p) {
    loc.push_back({
        x - (z > 1 && z < 8),
        y - (z > 5),
        (z % 4) > 1,
    });
  }
  ans += calc();

  // upward hexagon grid
  loc.clear();
  for (auto [x, y, z] : p) {
    loc.push_back({
        x - (z > 2 && z < 7),
        y - (z > 6 && z != 11),
        0,
    });
  }
  ans += calc() / 2;

  // downward hexagon grid
  loc.clear();
  for (auto [x, y, z] : p) {
    loc.push_back({
        x - (z != 0 && z < 9),
        y - (z == 0 || z > 4),
        1,
    });
  }
  ans += calc() / 2;

  // count by rhombi by chain
  map<int, map<int, int>> m1, m2, m3;
  for (auto [x, y, z] : p) {
    int dir = z % 6;
    if (dir == 0 || dir == 5) // horizontal
      m1[y][x - (z == 5 || z == 6)]++;
    else if (dir == 1 || dir == 2) // up-right
      m2[x][y - (z == 7 || z == 8)]++;
    else // up-left
      m3[x + y][y - (z == 9 || z == 10)]++;
  }
  auto chains = [&](map<int, map<int, int>> &m) {
    for (auto [k, v] : m) {
      int total = 0;
      for (auto [k2, v2] : v) {
        total += v2;
        ans -= (ll)v2 * (v2 - 1) / 2;
      }
      ans += (ll)total * (total - 1) / 2;
    }
  };
  chains(m1);
  chains(m2);
  chains(m3);
  cout << ans << '\n';
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int t;
  cin >> t;
  while (t--)
    solve();
}

完整解法 2 的简要做法（Ben）：

请注意，我们总是交替穿越三角形网格中的一条边与菱形网格中的一条边。让我们完全移除菱形网格，并将穿越三角形网格中每条边的代价翻倍。在此新网格中，所有点对距离之和可使用与完整解法 1 相同的方法计算。

为了从新网格中的距离得到原始网格中的距离，我们只需对每一对输入点添加一个在区间 $[-1, 1]$ 内的修正值。具体而言，若仅存在一对输入点，我们可以：

1. 将修正值初始化为 1。
2. 若存在一条三角形网格中的直线，它分隔了这两个输入点且可在第一步中穿越，则减去 1。
3. 若存在一条三角形网格中的直线，它分隔了这两个输入点且可在最后一步中穿越，则减去 1。
4. 若第 2 步和第 3 步均适用，且两次穿越的是同一条平行线，则加回 1。
5. 若两点位于同一菱形内，则减去 1。

对于所有点对，上述各部分的贡献可独立计算，时间复杂度为 $O(N \log N)$，再将它们相加得到最终答案。

翻译由 Qwen3-235B-A22B 完成