问题分析

本题是一道一道关于二维平面点集与几何区域计数的综合性问题，核心任务是计算在给定距离约束下，平面内满足条件的点对或区域数量。通过分析代码可知，问题涉及坐标变换、凸包优化、前缀和与差分等多种几何与算法技术，最终需要处理多组查询，返回不同距离限制下的计数结果。

算法思路

1. 坐标变换与预处理

为简化几何计算，首先对原始坐标进行变换：

• 对于点 $(x, y)$，根据 $(x + y)$ 的奇偶性分为两类处理：
  • 若为偶数：映射为四个点 $((x+y)/2, (x-y)/2)$、$((x+y)/2, (x-y)/2+1)$、$((x+y)/2+1, (x-y)/2)$、$((x+y)/2+1, (x-y)/2+1)$
  • 若为奇数：映射为五个点（类似对称扩展）
• 这种变换将原始平面距离计算转化为更简单的形式，便于后续几何操作。

2. 八方向对称处理

考虑平面的八重对称性，定义 8 种坐标变换方式（通过 vx[i] 和 vy[i] 实现），覆盖所有可能的对称方向：

• $o=0$：$(x, y) \rightarrow (x, y)$
• $o=1$：$(x, y) \rightarrow (x, -y)$
• $o=2$：$(x, y) \rightarrow (-y, x)$
• $o=3$：$(x, y) \rightarrow (-y, -x)$
• $o=4$：$(x, y) \rightarrow (-x, -y)$
• $o=5$：$(x, y) \rightarrow (-x, y)$
• $o=6$：$(x, y) \rightarrow (y, -x)$
• $o=7$：$(x, y) \rightarrow (y, x)$

每种变换用于处理特定方向上的点对关系，减少重复计算。

3. 凸包优化与序列生成

对于每种变换方向，通过排序和集合操作生成点的有序序列：

1. 按变换后的 $y$ 坐标（vy[i]）排序点集
2. 使用平衡树（set）维护当前有效的点，按 $x - y$ 坐标筛选，构建凸包相关的前驱关系
3. 记录每个点的前驱信息到 seq[o][x]，形成有序点列，用于后续距离计算

4. 差分与前缀和计算

为高效处理多组查询，采用差分与前缀和技术：

• 对每个方向和点，生成包含距离信息的事件序列 tms[o][i]
• 计算删除操作的边界 del[o][i]，标记无效区域
• 构建价值数组 vals，记录不同距离区间的计数贡献
• 对所有距离值离散化，通过差分数组 suma、sumb 计算区间和，最终生成前缀和数组 sum

5. 查询处理

对于每个查询距离 $k$：

• 通过二分查找定位离散化后的距离区间
• 计算该区间内的总贡献值，结合两类点集（q1 和 q2）的结果
• 根据查询距离的奇偶性，返回不同的组合结果：
  • 若 $k=0$：返回原始点数量 $n$
  • 若 $k=1$：返回 $v1 + v2 - n$
  • 若 $k \geq 2$：返回 $v1 + v2 - v1' - v2'$（其中 $v1', v2'$ 是距离 $k-1$ 的结果）

关键公式与复杂度

1. 坐标变换公式：

   • 偶数情况：$(x, y) \rightarrow \left( \frac{x+y}{2}, \frac{x-y}{2} \right)$ 及对称点
   • 奇数情况：$(x, y) \rightarrow \left( \frac{x+y+1}{2}, \frac{x-y+1}{2} \right)$ 及对称点 该变换将 Manhattan 距离转化为更易处理的形式，时间复杂度 $O(n)$。

2. 距离计算相关：

   • 点对距离通过变换后的坐标差计算：$\Delta v = vx[x] - vx[y]$，$\Delta u = vy[x] - vy[y]$
   • 区间贡献总和：$\text{sum}[i] = \text{sum}[i-1] + \frac{(l + r) \times (allv[i] - allv[i-1])}{2}$，其中 $l$ 和 $r$ 是区间端点的贡献值。

3. 整体时间复杂度：

   • 坐标变换与预处理：$O(n)$
   • 八方向处理：$O(8n \log n)$（排序与集合操作）
   • 差分与前缀和：$O(n + m)$（$m$ 为离散化后的值数量）
   • 查询处理：$O(q \log m)$
   • 总复杂度：$O(n \log n + q \log n)$，适合处理 $n \leq 5 \times 10^5$ 的数据规模。